Problem Description

Given a string s, count the number of non-empty substrings that contain only one distinct letter. Each substring must be contiguous and consist of the same repeated character. Return the total count of such substrings.

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Example:
Input: s = "aaaba"
Output: 8
Explanation: The substrings are: "a", "a", "a", "aa", "aa", "aaa", "b", "a".

Thought Process

The problem asks us to find all substrings within s that consist of only a single (repeated) character. The most straightforward (brute-force) approach would be to generate all possible substrings and count those that meet the requirement. However, this would be inefficient, especially for longer strings, as the number of substrings grows quadratically.

To optimize, we can observe that for every contiguous block of the same character (e.g., "aaa"), all its substrings are valid. For a block of length n, the count of such substrings is the sum of the first n natural numbers: n * (n + 1) / 2. This insight allows us to process the string in a single pass, grouping consecutive identical characters and summing the counts for each group.

Solution Approach

We'll solve the problem efficiently by counting contiguous groups of identical characters and summing the number of substrings for each group.

1. Initialize counters: Start with a variable to keep the total count, and another to track the length of the current group of same characters.
2. Iterate through the string: For each character in s (starting from the second character), check if it matches the previous character:
   • If yes, increment the current group length.
   • If no, compute the substrings for the previous group using group_length * (group_length + 1) / 2, add to the total, and reset the group length to 1.
3. Handle the last group: After the loop, add the substrings for the final group.
4. Return the total count.

This approach ensures we process the string in linear time and count all valid substrings efficiently.

Example Walkthrough

Let's walk through the example s = "aaaba":

• Start at index 0: current group is 'a', length = 1
• Index 1: 'a' (same as previous), group length = 2
• Index 2: 'a' (same as previous), group length = 3
• Index 3: 'b' (different), compute substrings for 'a': 3 * (3 + 1) / 2 = 6. Add to total. Reset group length = 1 for 'b'.
• Index 4: 'a' (different), compute substrings for 'b': 1 * (1 + 1) / 2 = 1. Add to total. Reset group length = 1 for 'a'.
• End of string: compute substrings for last 'a': 1 * (1 + 1) / 2 = 1. Add to total.
• Total = 6 + 1 + 1 = 8

Thus, the answer is 8, matching the expected output.

Time and Space Complexity

Brute-force approach:

• Time: O(N²), since there are O(N²) substrings to check.
• Space: O(1) extra space (not counting output).

• Time: O(N), since we scan the string once and do constant work per character.
• Space: O(1), as we only use a few variables for counting.

The optimized approach is much more efficient, especially for large inputs.

Summary

By recognizing that each block of consecutive identical characters can be handled in constant time, we reduce the problem from a quadratic brute-force solution to a simple linear scan. The key insight is using the formula for the number of substrings in a block, which makes the solution both elegant and efficient.

Code Implementation

class Solution:
    def countLetters(self, s: str) -> int:
        total = 0
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                total += count * (count + 1) // 2
                count = 1
        total += count * (count + 1) // 2
        return total
      

class Solution {
public:
    int countLetters(string s) {
        int total = 0, count = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1]) {
                count++;
            } else {
                total += count * (count + 1) / 2;
                count = 1;
            }
        }
        total += count * (count + 1) / 2;
        return total;
    }
};
      

class Solution {
    public int countLetters(String s) {
        int total = 0, count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                total += count * (count + 1) / 2;
                count = 1;
            }
        }
        total += count * (count + 1) / 2;
        return total;
    }
}
      

var countLetters = function(s) {
    let total = 0, count = 1;
    for (let i = 1; i < s.length; ++i) {
        if (s[i] === s[i-1]) {
            count++;
        } else {
            total += count * (count + 1) / 2;
            count = 1;
        }
    }
    total += count * (count + 1) / 2;
    return total;
};