Watch 2 video solutions for Count Substrings Without Repeating Character, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by Programming Live with Larry has 508 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting only of lowercase English letters. We call a substring special if it contains no character which has occurred at least twice (in other words, it does not contain a repeating character). Your task is to count the number of special substrings. For example, in the string "pop", the substring "po" is a special substring, however, "pop" is not special (since 'p' has occurred twice).
Return the number of special substrings.
A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "abcd", but "acd" is not.
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 <= 105s consists of lowercase English lettersProblem Overview: Given a string s, count how many substrings contain only unique characters. Any substring that repeats a character becomes invalid, so the goal is to efficiently track segments where all characters remain distinct.
Approach 1: Brute Force Enumeration (O(n²) time, O(k) space)
Start every substring at index i. Expand the substring character by character using index j. Maintain a set (or boolean map) to track characters already used in the current substring. If the next character is not in the set, add it and increment the count. If a duplicate appears, stop expanding from that start index and move to the next i. This approach checks all possible starting positions and stops early when duplicates appear, but the nested expansion still leads to O(n²) time in the worst case. Space complexity is O(k), where k is the character set size.
Approach 2: Sliding Window with Counting + Two Pointers (O(n) time, O(k) space)
Use the classic sliding window pattern with two pointers left and right. Expand right across the string while tracking characters in a hash structure such as a set or frequency map from a hash table. If a duplicate character appears, move left forward and remove characters from the window until the duplicate disappears. At every position of right, the window [left, right] contains only unique characters.
The key observation: if the window length is L = right - left + 1, then there are exactly L valid substrings ending at right. Each of these substrings starts anywhere from left to right. Add L to the total count. Continue expanding and shrinking the window as needed. Each character enters and leaves the window at most once, producing linear traversal of the string.
This method works because the window always represents the longest substring ending at right without repetition. Counting window sizes avoids explicitly enumerating every substring while still accounting for all valid ones. The algorithm runs in O(n) time and uses O(k) space for the character tracking structure. Since the input is a string, k is typically bounded by the alphabet size.
Recommended for interviews: The sliding window approach with two pointers is the expected solution. Brute force demonstrates that you understand substring enumeration and duplicate detection. The optimal sliding window shows you recognize the pattern used in many string problems involving unique characters, longest substrings, and dynamic window expansion.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set | O(n²) | O(k) | Small inputs or when demonstrating the baseline substring enumeration approach |
| Sliding Window (Counting + Two Pointers) | O(n) | O(k) | General case and interview solution; efficiently counts valid substrings using a dynamic window |