Solution Explanation for Counting Substrings with Only One Distinct Letter

This problem asks to count the number of substrings in a given string that contain only one distinct character. We can solve this efficiently using a two-pointer approach or a slightly optimized single-loop approach.

Approach 1: Two Pointers

This approach iterates through the string using two pointers, i and j.

• i marks the beginning of a substring containing only one distinct character.
• j iterates forward, extending the substring as long as the character remains the same.

Once j encounters a different character, the substring from i to j-1 contains only one distinct character. The number of substrings within this range is calculated using the formula for the sum of an arithmetic series: (length * (length + 1)) / 2, where length is j - i. This formula directly calculates the number of substrings of length 1, 2, ..., j-i.

The process repeats until the end of the string is reached.

Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice (once by i and once by j).

Space Complexity: O(1), as we use only a few integer variables.

Approach 2: Single Loop Optimization

This approach is similar to the two-pointer approach but slightly more concise. It keeps track of the count of consecutive identical characters (cnt) within the current substring. Each time a new character is added to the substring, the count is incremented and added directly to the total count (ans).

Time Complexity: O(n), similar to the two-pointer approach.

Space Complexity: O(1), constant extra space is used.

Code Implementation in Multiple Languages

Below are code implementations for both approaches in Python, Java, C++, Go, and TypeScript. Approach 1 (Two Pointers) is shown first, followed by Approach 2 (Optimized Single Loop).

Approach 1: Two Pointers

Python:

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
 

Java:

class Solution {
    public int countLetters(String s) {
        int ans = 0;
        for (int i = 0, n = s.length(); i < n;) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
            }
            ans += (1 + j - i) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int countLetters(string s) {
        int ans = 0;
        for (int i = 0, n = s.size(); i < n;) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            ans += (1 + j - i) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
};

Go:

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
}

TypeScript:

function countLetters(s: string): number {
    let ans = 0;
    let n = s.length;
    for (let i = 0; i < n; ) {
        let j = i;
        while (j < n && s[j] === s[i]) {
            j++;
        }
        ans += (j - i) * (j - i + 1) / 2;
        i = j;
    }
    return ans;
}

Approach 2: Optimized Single Loop

Python:

class Solution:
    def countLetters(self, s: str) -> int:
        ans = 0
        i, n = 0, len(s)
        while i < n:
            j = i
            cnt = 0
            while j < n and s[j] == s[i]:
                j += 1
                cnt += 1
                ans += cnt
            i = j
        return ans

Java: (Similar structure to Approach 1's Java code, just replace the ans += (1 + j - i) * (j - i) / 2; line with the cumulative sum calculation)

C++: (Similar structure to Approach 1's C++ code, just replace the ans += (1 + j - i) * (j - i) / 2; line with the cumulative sum calculation)

Go: (Similar structure to Approach 1's Go code, just replace the ans += (1 + j - i) * (j - i) / 2 line with the cumulative sum calculation)

The remaining languages (Java, C++, Go) would follow a similar pattern to the Python example for Approach 2, replacing the arithmetic series calculation with the direct cumulative sum. The TypeScript example would also be modified similarly. Note that the core logic remains the same: efficiently iterate and count the substrings.