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

Thinking

A one-letter substring lies inside a run of equal characters. A run of length \(L\) contributes \(L(L+1)/2\) substrings. Two pointers measure each run and add the triangular number, instead of listing \(O(n^2)\) substrings.

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

Thinking

Method 1 adds a closed triangular number per run. Method 2 adds \(1,2,\ldots,L\) while the run grows; the sum is the same triangle and reads as the number of one-letter substrings ending at the current index.

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
}