Count Substrings with Only One Distinct Letter

Problem

Given a string s, return the number of substrings that have onlyone distinct letter.

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.

Solution

Method 1 – Count Consecutive Characters

Intuition

Every substring with only one distinct letter is a substring of a run of consecutive identical characters. For a run of length n, the number of such substrings is n * (n + 1) / 2 (all possible substrings within the run).

Approach

1. Initialize a counter for the answer and a variable to track the length of the current run.
2. Iterate through the string:
   • If the current character is the same as the previous, increment the run length.
   • Otherwise, add the substrings from the previous run to the answer and reset the run length to 1.
3. After the loop, add the substrings from the last run.
4. Return the answer.

Code

C++

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

Go

type Solution struct{}
func (Solution) CountLetters(s string) int {
    ans, cnt := 0, 1
    n := len(s)
    for i := 1; i < n; i++ {
        if s[i] == s[i-1] {
            cnt++
        } else {
            ans += cnt * (cnt + 1) / 2
            cnt = 1
        }
    }
    ans += cnt * (cnt + 1) / 2
    return ans
}

Java

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

Kotlin

class Solution {
    fun countLetters(s: String): Int {
        var ans = 0
        var cnt = 1
        val n = s.length
        for (i in 1 until n) {
            if (s[i] == s[i-1]) cnt++
            else {
                ans += cnt * (cnt + 1) / 2
                cnt = 1
            }
        }
        ans += cnt * (cnt + 1) / 2
        return ans
    }
}

Python

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

Rust

impl Solution {
    pub fn count_letters(s: String) -> i32 {
        let s = s.as_bytes();
        let mut ans = 0;
        let mut cnt = 1;
        let n = s.len();
        for i in 1..n {
            if s[i] == s[i-1] {
                cnt += 1;
            } else {
                ans += cnt * (cnt + 1) / 2;
                cnt = 1;
            }
        }
        ans += cnt * (cnt + 1) / 2;
        ans
    }
}

TypeScript

class Solution {
    countLetters(s: string): number {
        let ans = 0, cnt = 1, n = s.length;
        for (let i = 1; i < n; ++i) {
            if (s[i] === s[i-1]) cnt++;
            else {
                ans += cnt * (cnt + 1) / 2;
                cnt = 1;
            }
        }
        ans += cnt * (cnt + 1) / 2;
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of s, since we scan the string once.
• 🧺 Space complexity: O(1), only a few variables are used.