Count Substrings Without Repeating Character

Count Substrings Without Repeating Character

What is this problem about?

The Count Substrings Without Repeating Character interview question requires you to find the total count of all substrings in a string that contain only unique characters. Unlike the problem of finding the longest such substring, here you must count every possible valid substring.

For example, in "abc", all substrings ("a", "b", "c", "ab", "bc", "abc") are valid because none of them contain duplicates. In "aba", the substring "aba" is invalid.

Why is this asked in interviews?

Interviews at Yandex and Oracle frequently feature this to test proficiency with the sliding window interview pattern. It’s a step up from the "Longest Unique Substring" problem because it requires a deeper understanding of how the window size relates to the total count. It demonstrates a candidate's ability to maintain a set or hash table of seen characters and efficiently update a running total.

Algorithmic pattern used

The Sliding Window (Two Pointers) combined with a Hash Table is the standard approach.

1. Initialize left = 0, right = 0, and a count = 0.
2. Move the right pointer to include a character.
3. If the character is already in the window (check using a frequency map or set), move the left pointer forward until the duplicate is removed.
4. After resolving duplicates, for a valid window from left to right, the number of unique substrings ending at right is exactly right - left + 1.
5. Add this window length to your total count.

Example explanation

s = "abac"

1. right = 0: "a". Valid. Count += 1 (Sub: "a").
2. right = 1: "ab". Valid. Count += 2 (Subs: "b", "ab"). Total = 3.
3. right = 2: "aba". Duplicate 'a'!
   • Shrink left to index 1. Window is now "ba".
   • Count += 2 (Subs: "a", "ba"). Total = 5.
4. right = 3: "bac". Valid. Count += 3 (Subs: "c", "ac", "bac"). Total = 8.

Common mistakes candidates make

• Miscalculating increments: Forgetting that each time the window expands, the number of new substrings is the current length of the window.
• Set management: Failing to remove characters from the set as the left pointer moves forward.
• Brute force: Trying to check all $N^2$ substrings for uniqueness, leading to $O(N^3)$ or $O(N^2)$ complexity.

Interview preparation tip

In sliding window problems, remember the "endpoint contribution" rule: the number of subarrays ending at index j that start at or after index i is exactly j - i + 1. This is a powerful way to count total valid subarrays in $O(N)$ time.