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
}

All Problems

All Solutions