Leetcode - Count Substrings with Only One Distinct Letter

https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/

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.

1. Use two pointers to find consecutive subarray

2. Count the times for (sub + 1)*sub/2

3. Continue

func countLetters(S string) int {
    left := 0
    right := left
    count := 0
    for right < len(S) {
        right = left + 1
        for right < len(S) && S[left] == S[right] {
            right++
        }
        sub := right - left
        count += (sub + 1) * sub/2
        left = right
    }
    return count
}

• 相关文章
• 全局相关文章