Count Substrings Without Repeating Character
01 · Problem
You are given a string s of lowercase English letters. A substring is special if no character appears in it more than once.
Return the number of special substrings of s. Substrings are counted by position, so equal text at different positions counts separately.
02 · Examples
s = "abcd"
10
All characters are distinct, so every one of the 4 * 5 / 2 = 10 substrings is special.
s = "xxyx"
6
The 4 single characters are special, plus "xy" and "yx". "xx" and every longer substring repeat an 'x'.
s = "abab"
7
Special substrings: 4 of length 1 and 3 of length 2 ("ab", "ba", "ab"). Every length-3 or longer substring repeats a letter.
03 · Constraints
- 011 <= s.length <= 105
- 02s consists only of lowercase English letters
- 03The answer fits in a 64-bit signed integer
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.