Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1180.html
1180. Count Substrings with Only One Distinct Letter
Level
Easy
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.
Solution
Loop over the string and find all longest substrings with only one distinct letter. For example, for string “aaaba”, the longest substrings with only one distinct letter are “aaa”, “b” and “a”. For each of the substrings, if the length of the substring is n
, then the number of substrings in the substring is n * (n - 1) / 2
. Add up the number of substrings in each such substring to obtain the answer.
-
class Solution { public int countLetters(String S) { int count = 0; int length = S.length(); int consecutive = 0; char prevChar = '0'; for (int i = 0; i < length; i++) { char c = S.charAt(i); if (c == prevChar) consecutive++; else { count += consecutive * (consecutive + 1) / 2; consecutive = 1; } prevChar = c; } if (consecutive > 0) count += consecutive * (consecutive + 1) / 2; return count; } }
-
// OJ: https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/ // Time: O(N) // Space: O(1) class Solution { public: int countLetters(string s) { int i = 0, N = s.size(), ans = 0; while (i < N) { int start = i; while (i < N && s[i] == s[start]) ++i; int len = i - start; ans += (1 + len) * len / 2; } 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; }