Count Substrings with Only One Distinct Letter

How it works

The string can be split into consecutive groups of identical characters. For each group of length L, the number of substrings containing only that character follows the arithmetic sequence formula: 1 + 2 + 3 + ... + L = L*(L+1)/2. We scan through the string, identify each group, and sum up the contributions.

Steps

1. Use two pointers, left and right, both starting at 0.
2. Move right through the string until a different character is found or the end is reached.
3. When a group ends (character changes or string ends):
   • Calculate the length of the group as (right - left).
   • Add the arithmetic sum: (length * (length + 1)) / 2 to the total.
   • Move left to right to start the next group.
4. Return the total count.

Complexity

• Time complexity: O(N)

• Space complexity: O(1) constant space

Where N is the length of the input string s.

Things to watch for

Using Wrong Formula for Counting Substrings

For a group of L identical consecutive characters, the number of valid substrings is L * (L + 1) / 2, not L or L * L. This arithmetic sum counts substrings of lengths 1, 2, 3, ..., L.

Forgetting to Process the Last Group

When iterating through the string to find groups of identical characters, the last group may not be processed if the loop only triggers on character changes. Ensure the final group is counted either by extending the loop to len(s) + 1 or by handling it after the loop ends.

class Solution:
    def countLetters(self, S: str) -> int:
        total = left = 0

        for right in range(len(S) + 1):
            if right == len(S) or S[left] != S[right]:
                len_substring = right - left
                # more details about the sum of the arithmetic sequence:
                # https://en.wikipedia.org/wiki/Arithmetic_progression#Sum
                total += (1 + len_substring) * len_substring // 2
                left = right

        return total

class Solution {
public:
    int countLetters(string s) {
        int total = 0;
        for (int left = 0, right = 0; right <= s.length(); right++) {
            if (right == s.length() || s[left] != s[right]) {
                int lenSubstring = right - left;
                // more details about the sum of the arithmetic sequence:
                // https://en.wikipedia.org/wiki/Arithmetic_progression#Sum
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }

        return total;
    }
};