1180. Count Substrings with Only One Distinct Letter 🔒

Description

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

 

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.

Solutions

Solution 1: Two Pointers

We can use two pointers, where pointer \(i\) points to the start of the current substring, and pointer \(j\) moves to the right to the first position that is different from \(s[i]\). Then, \([i,..j-1]\) is a substring with \(s[i]\) as the only character, and its length is \(j-i\). Therefore, the number of substrings with \(s[i]\) as the only character is \(\frac{(j-i+1)(j-i)}{2}\), which is added to the answer. Then, we set \(i=j\) and continue to traverse until \(i\) exceeds the range of string \(s\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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

Solution 2

Python3JavaC++Go

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

class Solution {
    public int countLetters(String s) {
        int ans = 0;
        int i = 0, n = s.length();
        while (i < n) {
            int j = i;
            int cnt = 0;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
                ans += ++cnt;
            }
            i = j;
        }
        return ans;
    }
}

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

func countLetters(s string) (ans int) {
    i, n := 0, len(s)
    for i < n {
        j := i
        cnt := 0
        for j < n && s[j] == s[i] {
            j++
            cnt++
            ans += cnt
        }
        i = j
    }
    return
}

Comments