Count Substrings With Only One Distinct Letter - Leetcode Solution

Problem statement:

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 "a", "a", "a", "b", "a", "aa", "aa", "aaa".

Example 2: Input: S = "aaaaaaaaaa" Output: 55

Approach:

We can solve this problem using two pointers approach. At any given time, we will maintain two pointers, i and j, such that the substring (i, j) has only one distinct letter. The idea is fairly simple, we can iterate through the string and if the current character is same as the previous character, we move the end pointer j, otherwise, we calculate the number of substrings that end at i, which is (j-i+1) * (j-i+2) / 2. We then reset i to j and update j to the next character.

Solution:

class Solution:
    def countLetters(self, S: str) -> int:
        i, j, n = 0, 0, len(S)
        count = 0
        while j < n:
            if S[i] == S[j]:
                j += 1
            else:
                count += (j-i)*(j-i+1)//2
                i = j
        count += (j-i)*(j-i+1)//2
        return count

Time Complexity: O(n)

Space Complexity: O(1)

Explanation:

1. We initialize i, j to 0 and count to 0.
2. We iterate through the string until j < n.
3. If S[i] == S[j], we move j to the next character.
4. If S[i] != S[j], we calculate the number of substrings that end at i and add it to the count. We then reset i to j and move j to the next character.
5. We finally calculate the number of substrings that end at j and add it to the count.
6. We return the count.

Thus, we can solve the problem using two pointers approach.

1