Count Substrings Without Repeating Character

Problem Statement

In this problem, we are provided with a string s, which is composed solely of lowercase English alphabets. We need to calculate the number of special substrings contained within this string. A substring is deemed special if it is composed of unique characters without any repetitions. Our objective is to identify all such substrings, count them, and return the total count. Understanding what constitutes a substring is crucial; it is a sequence of characters derived from the string such that it is a contiguous block within the string.

Examples

Example 1

Input:

s = "abcd"

Output:

10

Explanation:

Since each character occurs once, every substring is a special substring. We have 4 substrings of length one, 3 of length two, 2 of length three, and 1 substring of length four. So overall there are 4 + 3 + 2 + 1 = 10 special substrings.

Example 2

Input:

s = "ooo"

Output:

3

Explanation:

Any substring with a length of at least two contains a repeating character. So we have to count the number of substrings of length one, which is 3.

Example 3

Input:

s = "abab"

Output:

7

Explanation:

Special substrings are as follows (sorted by their start positions):
Special substrings of length 1: "a", "b", "a", "b"
Special substrings of length 2: "ab", "ba", "ab"
And it can be shown that there are no special substrings with a length of at least three. So the answer would be 4 + 3 = 7.

Constraints

• 1 <= s.length <= 105
• s consists of lowercase English letters

Approach and Intuition

The key challenge is to find substrings that do not contain any repeating characters and then to keep a count of all such substrings. Here’s a step-by-step breakdown of how we might approach this:

1. Understanding Substring Properties: A substring is special if all characters within it are unique. We begin by examining the smallest substrings (single characters) which are always special.

2. Counting Single-Character Substrings: Given that every single character is unique in itself, there are as many single-character special substrings as there are characters in the string s.

3. Expanding the Search to Larger Substrings: To manage this efficiently, we can use a sliding window approach. Start with a window covering the initial part of the string and expand the window until a repeating character is encountered.

4. Tracking Repeated Characters: Use data structures like hashmaps or sets to keep track of the characters in the current window and detect repetitions. When a repeat is detected, adjust the window to exclude the repeat and continue counting.

5. Counting Non-Repeating Substrings: Expand the window from each character in the string unless a repeat is found. For each initial position, the window can vary in size from 1 up to the length of the substring that can be formed without repeating characters.

6. Optimization Consideration: Directly calculating the substring count using brute force can be highly inefficient, especially for large strings. Instead, calculating potential substrings via the sliding window ensures that you only examine feasible substrings, saving computational time.

Example Scenario from Example 3:

When we analyze "abab", starting with the first character:

• Begin with "a" — it’s valid.
• Expand to "ab" — still valid.
• Try "aba" — not valid as 'a' repeats. Move the window to start from the next character. Continue this until all characters are examined as starting points.

In this illustration, the effective handling of the sliding window in conjunction with set operations (for tracking characters within the current window) would allow for efficient detection and counting of all special substrings.

Solutions

class Solution {
public:
    int countUniqueSubstrings(string str) {
        int count = 0;
        int left = 0;
        int letterFrequency[26] = {0};
        for (int right = 0; right < str.size(); right++) {
            letterFrequency[str[right] - 'a']++;
    
            while (letterFrequency[str[right] - 'a'] > 1) {
                letterFrequency[str[left] - 'a']--;
                left++;
            }
    
            count += (right - left + 1);
        }
    
        return count;
    }
};