Problem Description

You are given a string s consisting only of lowercase English letters. A substring is called special if it contains no character that appears more than once (no repeating characters).

Your task is to count the total number of special substrings in the given string.

For example, in the string "pop":

• "p" is special (appears at positions 0 and 2, counted separately)
• "o" is special
• "po" is special
• "op" is special
• "pop" is NOT special because the character 'p' appears twice in it

A substring is a contiguous sequence of characters within a string. For instance, "abc" is a substring of "abcd", but "acd" is not.

The solution uses a sliding window approach with two pointers. The algorithm maintains a window [j, i] where all characters appear at most once. For each position i, it counts how many special substrings end at that position. Since any substring of a special substring is also special, if the window [j, i] contains all unique characters, then all substrings ending at i and starting from any position between j and i are special. This gives us exactly i - j + 1 special substrings ending at position i.

Intuition

The key observation is that if we have a substring with all unique characters, then every substring within it also has unique characters. For example, if "abcd" has all unique characters, then "abc", "bcd", "ab", "bc", "cd", "a", "b", "c", and "d" all have unique characters too.

This leads us to think about maintaining a window of characters where no character repeats. As we expand this window by adding characters from the right, we can count how many valid substrings end at each position.

Consider when we're at position i and we have a valid window from position j to i (all characters in s[j...i] are unique). How many special substrings end at position i?

• The substring from j to i is special
• The substring from j+1 to i is special
• The substring from j+2 to i is special
• ...
• The substring from i to i (just the character itself) is special

That's exactly i - j + 1 special substrings ending at position i.

When we encounter a character that already exists in our current window, we need to shrink the window from the left until that character appears only once. This ensures our window always maintains the property of having all unique characters.

By processing each position and counting the special substrings ending at that position, we avoid the need to check every possible substring individually, reducing the time complexity from O(n³) (checking all substrings) to O(n) (single pass with sliding window).

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a sliding window technique with two pointers to efficiently count all special substrings.

Data Structures Used:

• A Counter (hash map) to track the frequency of each character in the current window
• Two pointers: j (left boundary) and i (right boundary) of the window

Algorithm Steps:

1. Initialize variables:

   • cnt: A Counter to store character frequencies in the current window
   • ans: Accumulator for the total count of special substrings
   • j: Left pointer starting at position 0

2. Expand the window by iterating through each character:

   for i, c in enumerate(s):
       cnt[c] += 1

   For each position i, we add the character s[i] to our window by incrementing its count in cnt.

3. Shrink the window if necessary:

   while cnt[c] > 1:
       cnt[s[j]] -= 1
       j += 1

   If the newly added character c appears more than once (meaning we have a duplicate), we need to shrink the window from the left. We keep removing characters from the left (decrementing their count and moving j right) until the character c appears exactly once.

4. Count special substrings ending at position i:

   ans += i - j + 1

   After ensuring the window [j, i] contains all unique characters, we know that all substrings ending at i and starting from any position between j and i are special. The count of such substrings is i - j + 1.

5. Return the total count: After processing all positions, ans contains the total number of special substrings.

Time Complexity: O(n) where n is the length of the string. Each character is visited at most twice (once by the right pointer and once by the left pointer).

Space Complexity: O(min(n, 26)) for the Counter, which in the worst case stores all unique characters in the string (at most 26 for lowercase English letters).

Example Walkthrough

Let's trace through the algorithm with the string s = "abcab".

Initial Setup:

• cnt = {} (empty counter)
• ans = 0 (total count)
• j = 0 (left pointer)

Step 1: i = 0, c = 'a'

• Add 'a' to window: cnt = {'a': 1}
• No duplicates (cnt['a'] = 1), so no shrinking needed
• Count substrings ending at position 0: ans += 0 - 0 + 1 = 1
• Special substrings found: ["a"]
• Running total: ans = 1

Step 2: i = 1, c = 'b'

• Add 'b' to window: cnt = {'a': 1, 'b': 1}
• No duplicates (cnt['b'] = 1), so no shrinking needed
• Count substrings ending at position 1: ans += 1 - 0 + 1 = 2
• Special substrings found: ["ab", "b"]
• Running total: ans = 3

Step 3: i = 2, c = 'c'

• Add 'c' to window: cnt = {'a': 1, 'b': 1, 'c': 1}
• No duplicates (cnt['c'] = 1), so no shrinking needed
• Count substrings ending at position 2: ans += 2 - 0 + 1 = 3
• Special substrings found: ["abc", "bc", "c"]
• Running total: ans = 6

Step 4: i = 3, c = 'a'

• Add 'a' to window: cnt = {'a': 2, 'b': 1, 'c': 1}
• Duplicate detected! cnt['a'] = 2, need to shrink:
  • Remove s[0] = 'a': cnt = {'a': 1, 'b': 1, 'c': 1}, j = 1
  • Now cnt['a'] = 1, stop shrinking
• Count substrings ending at position 3: ans += 3 - 1 + 1 = 3
• Special substrings found: ["bca", "ca", "a"]
• Running total: ans = 9

Step 5: i = 4, c = 'b'

• Add 'b' to window: cnt = {'a': 1, 'b': 2, 'c': 1}
• Duplicate detected! cnt['b'] = 2, need to shrink:
  • Remove s[1] = 'b': cnt = {'a': 1, 'b': 1, 'c': 1}, j = 2
  • Now cnt['b'] = 1, stop shrinking
• Count substrings ending at position 4: ans += 4 - 2 + 1 = 3
• Special substrings found: ["cab", "ab", "b"]
• Running total: ans = 12

Final Result: The total number of special substrings is 12.

The algorithm efficiently identifies all special substrings by maintaining a sliding window of unique characters and counting valid substrings ending at each position, avoiding the need to check every possible substring individually.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. Although there is a nested while loop inside the for loop, each character in the string is visited at most twice - once when the right pointer i includes it, and once when the left pointer j excludes it. The right pointer i moves from index 0 to n-1 exactly once, and the left pointer j also moves from 0 to at most n-1 throughout the entire execution. Therefore, the total number of operations is at most 2n, which simplifies to O(n).

The space complexity is O(C), where C is the size of the character set. The Counter object cnt stores at most C distinct characters. Since the problem deals with lowercase English letters, C = 26, making the space complexity O(26) = O(1) in practical terms, though it's more precisely expressed as O(C) to account for the dependency on the character set size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Count All Valid Substrings at Each Position

The Pitfall: A common mistake is to increment the result by 1 for each valid window position, rather than counting all valid substrings ending at the current position. This would look like:

# INCORRECT approach
for right, char in enumerate(s):
    char_count[char] += 1
    while char_count[char] > 1:
        char_count[s[left]] -= 1
        left += 1
    result += 1  # Wrong! Only counts one substring per position

This only counts the longest special substring ending at each position, missing all the shorter valid substrings.

Why This Happens: The sliding window maintains the longest valid substring ending at position right, but we need to count ALL valid substrings ending there, not just the longest one.

The Solution: Add right - left + 1 to the result, which accounts for all substrings ending at right:

• Substring from left to right (length: right - left + 1)
• Substring from left + 1 to right (length: right - left)
• ... and so on ...
• Substring from right to right (length: 1)

2. Not Properly Cleaning Up the Counter

The Pitfall: When shrinking the window, forgetting to remove characters with zero count from the Counter:

# Potentially problematic if you check counter size
while char_count[char] > 1:
    char_count[s[left]] -= 1
    # Should consider removing if count becomes 0
    left += 1

Why This Matters: While the provided solution works correctly (since we only check char_count[char] > 1), if you modify the code to check the Counter's size or iterate through its keys, having zero-count entries could cause issues.

The Solution: Clean up zero entries if needed for other operations:

while char_count[char] > 1:
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]
    left += 1

3. Off-by-One Error in Counting Substrings

The Pitfall: Using right - left instead of right - left + 1:

# INCORRECT
result += right - left  # Misses counting the single character substring

Why This Happens: When calculating the number of elements in a range [left, right] inclusive, the formula is right - left + 1, not right - left.

Example to Illustrate: If left = 2 and right = 4, the window contains positions [2, 3, 4]:

• Substrings: [2,4], [3,4], [4,4]
• Count: 3 substrings = 4 - 2 + 1 ✓
• Not: 2 substrings = 4 - 2 ✗