Count Substrings with No Repeated Characters

Question

This question asks the candidate to determine the number of substrings in a given string that contain no repeated characters.

Codemia · Accepted Answer

To solve the problem of counting substrings with no repeated characters, we can utilize the sliding window technique. This approach allows us to maintain a dynamic window of characters while iterating through the string, ensuring that we only count substrings that meet the criteria of having unique characters.

1. Initialize a hash set to store characters in the current window.
2. Use two pointers, `start` and `end`, to represent the current substring's boundaries.
3. Iterate through the string with the `end` pointer:
   - If the character at `end` is not in the set, add it to the set and count all substrings ending at `end`.
   - If it is in the set, move the `start` pointer to the right until the character can be added without duplicates.
4. Continue this process until `end` reaches the end of the string.
5. Return the total count of unique substrings.

The time complexity of this algorithm is O(n), where n is the length of the string. This is because each character is processed at most twice (once by `end` and once by `start`). The space complexity is O(min(n, m)), where m is the size of the character set (e.g., 26 for lowercase letters).

```python
def count_unique_substrings(s):
    char_set = set()
    start = 0
    count = 0
    for end in range(len(s)):
        while s[end] in char_set:
            char_set.remove(s[start])
            start += 1
        char_set.add(s[end])
        count += end - start + 1
    return count
```
This function counts and returns the number of substrings without repeated characters.

Consider edge cases such as an empty string, which should return 0, or a string with all identical characters, which should also return the correct count of unique substrings (which would be the length of the string).

Count Substrings with No Repeated Characters

NVIDIA

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

NVIDIA Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string