Count Substrings Without Repeating Character - Solution & Explanation
Problem Statement
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 <= 105sconsists of lowercase English letters
Approach Overview
Problem 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.
Solution
We use two pointers j and i to represent the left and right boundaries of the current substring, and an array cnt of length 26 to count the occurrence of each character in the current substring. We traverse the string from left to right. Each time we traverse to position i, we increase the occurrence of s[i], and then check whether s[i] appears at least twice. If so, we need to decrease the occurrence of s[j] and move j one step to the right, until the occurrence of s[i] does not exceed once. In this way, we get the length of the longest special substring ending with s[i], which is i - j + 1, so the number of special substrings ending with s[i] is i - j + 1. Finally, we add up the number of special substrings ending at each position to get the answer.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string s, and C is the size of the character set. In this problem, the character set consists of lowercase English letters, so C = 26.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
2743. Count Substrings Without Repeating Character - Week 4/5 Leetcode June Challenge • Programming Live with Larry • 543 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Count Substrings Without Repeating Character easy or hard?
Count Substrings Without Repeating Character Python/Java solution
How to solve Count Substrings Without Repeating Character in O(n)?
What is the best approach for Count Substrings Without Repeating Character?
Is Count Substrings Without Repeating Character asked at Google/Amazon/Meta?
What data structure is used in Count Substrings Without Repeating Character?
What is the time complexity of Count Substrings Without Repeating Character?
Ready to solve this problem?
Practice Count Substrings Without Repeating Character with our built-in code editor and test cases.
Practice on FleetCode