Given a string s, return the number of substrings that have only one distinct letter.
Example 1:
Input: s = "aaaba" Output: 8 Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b". "aaa" occurs 1 time. "aa" occurs 2 times. "a" occurs 4 times. "b" occurs 1 time. So the answer is 1 + 2 + 4 + 1 = 8.
Example 2:
Input: s = "aaaaaaaaaa" Output: 55
Constraints:
1 <= s.length <= 1000s[i] consists of only lowercase English letters.We can use two pointers, where pointer i points to the start of the current substring, and pointer j moves to the right to the first position that is different from s[i]. Then, [i,..j-1] is a substring with s[i] as the only character, and its length is j-i. Therefore, the number of substrings with s[i] as the only character is \frac{(j-i+1)(j-i)}{2}, which is added to the answer. Then, we set i=j and continue to traverse until i exceeds the range of string s.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Java
C++
Go
TypeScript
Java
C++
Go
| Approach | Complexity |
|---|---|
| Two Pointers | — |
| Default Approach | — |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Count Substrings with Only One Distinct Letter with our built-in code editor and test cases.
Practice on FleetCode