Count Substrings with Only One Distinct Letter
Sum of triangular numbers — each run of length k contributes k*(k+1)/2 single-letter substrings.
3 min read
string math counting
Problem#
Count the number of substrings containing exactly one distinct letter.
Examples#
"aaaba"→8(runs"aaa"contributes 6,"b"contributes 1,"a"contributes 1)."aaaaaaaaaa"→55.
Constraints#
1 <= S.length <= 1000.
Approach#
Scan the string into maximal single-letter runs. A run of length k contributes k * (k + 1) / 2 valid substrings. Sum across runs.
Solution#
class Solution {public: int countLetters(string s) { long long ans = 0, run = 0; for (int i = 0; i < (int)s.size(); ++i) { if (i == 0 || s[i] == s[i-1]) ++run; else run = 1; ans += run; } return (int)ans; }};func countLetters(s string) int { ans, run := 0, 0 for i := 0; i < len(s); i++ { if i == 0 || s[i] == s[i-1] { run++ } else { run = 1 } ans += run } return ans}class Solution: def countLetters(self, s: str) -> int: ans, run = 0, 0 for i in range(len(s)): if i == 0 or s[i] == s[i - 1]: run += 1 else: run = 1 ans += run return ansfunction countLetters(s) { let ans = 0, run = 0; for (let i = 0; i < s.length; i++) { if (i === 0 || s[i] === s[i - 1]) run++; else run = 1; ans += run; } return ans;}class Solution { public int countLetters(String s) { long ans = 0, run = 0; for (int i = 0; i < s.length(); i++) { if (i == 0 || s.charAt(i) == s.charAt(i - 1)) run++; else run = 1; ans += run; } return (int) ans; }}function countLetters(s: string): number { let ans = 0, run = 0; for (let i = 0; i < s.length; i++) { if (i === 0 || s[i] === s[i - 1]) run++; else run = 1; ans += run; } return ans;}Editorial#
Incremental “add run at each step” is the streaming version of sum k*(k+1)/2 — at step i, run is the length of the current run ending at i, and that’s exactly the number of new single-letter substrings ending at i.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#