LeetCode 2743 - Count Substrings Without Repeating Character

LeetCode Problem 2743

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem asks us to count how many substrings of a given string contain only unique characters. A substring is considered special if no character appears more than once inside that substring.

We are given a string s containing only lowercase English letters. For every possible contiguous substring, we need to determine whether all characters inside it are distinct. If they are, we count that substring toward the final answer.

For example, if s = "abcd", every substring is valid because no character repeats anywhere. The total number of substrings in a string of length 4 is:

• Length 1 substrings: 4
• Length 2 substrings: 3
• Length 3 substrings: 2
• Length 4 substrings: 1

So the answer is 10.

The constraints are important:

• 1 <= s.length <= 10^5
• Only lowercase English letters appear

A string length of 10^5 means an algorithm with quadratic complexity, such as checking every substring independently, will be too slow. We need something close to linear time.

Several edge cases are important:

• A string with all identical characters, such as "aaaa", where only single-character substrings are valid.
• A string with all unique characters, such as "abcdef", where every substring is valid.
• Strings where repeated characters appear frequently and force the valid substring window to shrink often, such as "abababab".

The key challenge is efficiently counting all substrings with unique characters without explicitly generating every substring.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible substring and check whether it contains duplicate characters.

For each starting index:

1. Extend the substring one character at a time.
2. Maintain a set of characters already seen.
3. If the next character already exists in the set, stop extending because any longer substring will also contain duplicates.
4. Otherwise, count the substring as valid.

This approach is correct because it explicitly checks every candidate substring.

However, in the worst case, such as "abcdef...", every substring must be examined. Since there are O(n^2) substrings, the solution becomes too slow for n = 10^5.

Optimal Sliding Window Approach

The key observation is that we do not need to restart duplicate checking from scratch for every substring.

Suppose we maintain a window [left, right] where all characters are unique. When we expand the window by moving right, there are two possibilities:

• The new character is not already inside the window, so the window remains valid.
• The new character already exists inside the window, so we move left forward until the duplicate is removed.

At every position right, all substrings ending at right and starting anywhere between left and right are valid.

If the current valid window length is:

window_size = right - left + 1

then exactly window_size special substrings end at index right.

This transforms the problem into a linear-time sliding window solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) to O(26)	Checks every substring individually
Optimal	O(n)	O(1) to O(26)	Sliding window with character tracking

Algorithm Walkthrough

1. Initialize two pointers, left and right, to represent the current sliding window.

The window will always maintain the invariant that all characters inside it are unique. 2. Create a data structure to track character occurrences.

Since the string only contains lowercase English letters, we can use:

• A hash set
• A frequency array of size 26
• A hash map storing last seen positions

A last-seen index map is particularly efficient. 3. Iterate through the string using right.

For each character s[right], check whether it already exists inside the current window. 4. If the character was previously seen inside the current valid window, move left.

Specifically, if:

last_seen[s[right]] >= left

then the character repeats within the window, so update:

left = last_seen[s[right]] + 1

This removes the duplicate occurrence. 5. Update the character's most recent position.

Store:

last_seen[s[right]] = right

6. Count valid substrings ending at right.

The current window length is:

right - left + 1

Every substring ending at right and starting anywhere from left to right is valid.

Add this value to the answer. 7. Continue until the entire string has been processed.

Why it works

The sliding window always maintains a substring with no repeated characters. Whenever a duplicate appears, the left boundary moves just enough to remove the repeated occurrence.

For every position right, the algorithm counts all valid substrings ending at that index exactly once. Since every valid substring has a unique ending index, the final total is correct.

Python Solution

class Solution:
    def numberOfSpecialSubstrings(self, s: str) -> int:
        last_seen = {}
        
        left = 0
        answer = 0
        
        for right, char in enumerate(s):
            if char in last_seen and last_seen[char] >= left:
                left = last_seen[char] + 1
            
            last_seen[char] = right
            
            answer += right - left + 1
        
        return answer

The implementation uses a dictionary called last_seen to store the most recent index where each character appeared.

The variable left marks the beginning of the current valid window. As we iterate through the string with right, we check whether the current character already exists inside the window.

If a duplicate is found, we move left just past the previous occurrence of that character. This guarantees the window contains only unique characters.

After updating the window, we compute how many valid substrings end at the current index. Since every starting position between left and right forms a valid substring, the number added is:

right - left + 1

The algorithm processes each character at most twice, once when expanding the window and once when moving the left boundary, which gives linear complexity.

Go Solution

func numberOfSpecialSubstrings(s string) int {
    lastSeen := make(map[byte]int)

    left := 0
    answer := 0

    for right := 0; right < len(s); right++ {
        char := s[right]

        if prevIndex, exists := lastSeen[char]; exists && prevIndex >= left {
            left = prevIndex + 1
        }

        lastSeen[char] = right

        answer += right - left + 1
    }

    return answer
}

The Go implementation follows the same logic as the Python version.

A map[byte]int stores the most recent occurrence index for each character. Since the input contains only lowercase English letters, treating characters as bytes is sufficient.

Go does not have Python's tuple unpacking or dictionary membership syntax, so the code uses:

prevIndex, exists := lastSeen[char]

to determine whether the character has appeared before.

The result fits safely inside a standard Go int because the maximum number of substrings for n = 10^5 is:

100000 * 100001 / 2 = 5,000,050,000

On LeetCode's 64-bit systems, int is sufficient. If portability to 32-bit systems were required, int64 would be safer.

Worked Examples

Example 1

Input:

s = "abcd"

right	char	left	window	new substrings	total
0	a	0	"a"	1	1
1	b	0	"ab"	2	3
2	c	0	"abc"	3	6
3	d	0	"abcd"	4	10

Final answer:

10

Every substring is valid because all characters are unique.

Example 2

Input:

s = "ooo"

right	char	left	window	new substrings	total
0	o	0	"o"	1	1
1	o	1	"o"	1	2
2	o	2	"o"	1	3

Final answer:

3

Each repeated o forces the window to shrink to length 1.

Example 3

Input:

s = "abab"

right	char	left	window	new substrings	total
0	a	0	"a"	1	1
1	b	0	"ab"	2	3
2	a	1	"ba"	2	5
3	b	2	"ab"	2	7

Final answer:

7

When a duplicate appears, the left pointer moves past the previous occurrence.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(1)	At most 26 lowercase letters are stored

The sliding window moves monotonically from left to right. Each character enters and leaves the window at most once, which guarantees linear runtime.

Although a hash map is used, the alphabet size is fixed at 26 lowercase letters, so the auxiliary space remains constant.

Test Cases

solution = Solution()

assert solution.numberOfSpecialSubstrings("abcd") == 10  # all unique
assert solution.numberOfSpecialSubstrings("ooo") == 3  # all identical
assert solution.numberOfSpecialSubstrings("abab") == 7  # alternating duplicates

assert solution.numberOfSpecialSubstrings("a") == 1  # single character
assert solution.numberOfSpecialSubstrings("aa") == 2  # only single-char substrings valid
assert solution.numberOfSpecialSubstrings("ab") == 3  # all substrings valid

assert solution.numberOfSpecialSubstrings("abcabcbb") == 18  # repeated pattern
assert solution.numberOfSpecialSubstrings("abcdef") == 21  # maximum valid substrings
assert solution.numberOfSpecialSubstrings("abba") == 6  # duplicate forces left jump
assert solution.numberOfSpecialSubstrings("dvdf") == 9  # window expands after duplicate removal

assert solution.numberOfSpecialSubstrings("abcdefghijklmnopqrstuvwxyz") == 351  # full alphabet unique

Test	Why
"abcd"	Every substring is valid
"ooo"	Repeated characters everywhere
"abab"	Alternating duplicates
"a"	Smallest possible input
"aa"	Duplicate immediately appears
"ab"	Simple unique case
"abcabcbb"	Multiple duplicate resets
"abcdef"	Long unique window
"abba"	Duplicate inside middle of window
"dvdf"	Window recovery after duplicate
"abcdefghijklmnopqrstuvwxyz"	Maximum distinct lowercase letters

Edge Cases

A very important edge case is a string where every character is identical, such as "aaaaaa". A naive implementation may incorrectly count longer substrings that contain duplicates. In the sliding window solution, each repeated character immediately forces the left boundary to move forward, ensuring the valid window length never exceeds 1.

Another important case is a completely unique string such as "abcdef". In this situation, the sliding window continuously expands without shrinking. The implementation correctly counts all substrings because every prefix ending at each position is valid.

A more subtle edge case occurs when the duplicate character appears inside the current window but not at the immediate previous position, such as "abba". When processing the second 'b', the left pointer moves forward. Later, when processing the final 'a', the algorithm must avoid moving left backward. The condition:

last_seen[char] >= left

ensures we only react to duplicates that are still inside the active window.

Another tricky scenario is repeated alternating patterns such as "abababab". The window repeatedly shrinks and expands. The implementation handles this efficiently because both pointers only move forward, preserving linear complexity even under frequent duplicate encounters.