LeetCode 1180. Count Substrings with Only One Distinct Letter

Description

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.

Example 2:

Input: s = "aaaaaaaaaa"
Output: 55

Constraints:

  • 1 <= s.length <= 1000
  • s[i] consists of only lowercase English letters.

Explanation

The simplest solution would be to check substrings and find those with only one distinct character.

Python Solution

class Solution:
    def countLetters(self, S: str) -> int:
        
        count = 0
        
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                
                sub = S[i:j]
                sub_set = set(sub)
                
                if len(sub_set) == 1:
                    count += 1
                else:
                    break
        
        return count
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.