Count Substrings with Only One Distinct Letter

Problem Statement

The challenge presented is to count the total number of substrings within a given string s such that each substring contains exactly one unique character. This specifically focuses on identifying substrings where all characters are identical. Each substring counts independently based on its occurrence, even if they are of the same set of characters but at different positions or lengths within the main string.

Examples

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.

Approach and Intuition

To solve the problem, it's essential to understand substrings and how we might systematically count these specific kinds.

1. Iterate through the string s to find continuous blocks (segments) where the character does not change.
2. For each segment of the same character, calculate the number of possible substrings. If a segment has a length n, the number of such substrings can be computed as the sum of the first n natural numbers (which is n*(n+1)/2).
3. Accumulate the counts for each character segment to get the total number of substrings for s.

Breakdown

• Initialization: Start with a total count of 0.
• Traverse the string: As you iterate, if a character is the same as the previous one, extend the current segment. If not, calculate possible substrings from the previous segment and reset counters for the new segment.
• Character Segment Calculation: For a sequence of character length, l, use the formula l*(l+1)/2 to add to the total count.
• Edge Case Handling: Ensure to calculate the contribution of the last segment after the loop because it might not trigger a calculation in the loop.

Illustration

Using example 2 where s = "aaaaaaaaaa":

• The entire string is a single segment of length 10.
• Calculate the substrings for this segment: [ \frac{10 \times (10 + 1)}{2} = 55 ]
• The result of 55 shows the complete substrings count for 10 consecutive 'a's.

Solutions

class Solution {
    public int sumOfRepeatingChars(String str) {
        int sum = 1, consecutive = 1;
        for (int index = 1; index < str.length(); index++) {
            if (str.charAt(index) == str.charAt(index - 1)) {
                consecutive++;
            } else {
                consecutive = 1;
            }
            sum += consecutive;
        }
        return sum;
    }
}