Welcome to Subscribe On Youtube
1180. Count Substrings with Only One Distinct Letter
Description
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 <= 1000
s[i]
consists of only lowercase English letters.
Solutions
Solution 1: Two Pointers
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,..j1]$ is a substring with $s[i]$ as the only character, and its length is $ji$. Therefore, the number of substrings with $s[i]$ as the only character is $\frac{(ji+1)(ji)}{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)$.

class Solution { public int countLetters(String s) { int ans = 0; for (int i = 0, n = s.length(); i < n;) { int j = i; while (j < n && s.charAt(j) == s.charAt(i)) { ++j; } ans += (1 + j  i) * (j  i) / 2; i = j; } return ans; } }

class Solution { public: int countLetters(string s) { int ans = 0; for (int i = 0, n = s.size(); i < n;) { int j = i; while (j < n && s[j] == s[i]) { ++j; } ans += (1 + j  i) * (j  i) / 2; i = j; } return ans; } };

class Solution: def countLetters(self, s: str) > int: n = len(s) i = ans = 0 while i < n: j = i while j < n and s[j] == s[i]: j += 1 ans += (1 + j  i) * (j  i) // 2 i = j return ans

func countLetters(s string) int { ans := 0 for i, n := 0, len(s); i < n; { j := i for j < n && s[j] == s[i] { j++ } ans += (1 + j  i) * (j  i) / 2 i = j } return ans }

function countLetters(s: string): number { let ans = 0; const n = s.length; for (let i = 0; i < n; ) { let j = i; let cnt = 0; while (j < n && s[j] === s[i]) { ++j; ans += ++cnt; } i = j; } return ans; }