1180. Count Substrings with Only One Distinct Letter

class Solution:
    def countLetters(self, s: str) -> int:
        """
        tc O(N) sc O(N)
        main idea: sliding window.  
                number of substring can be caculated by accumutive sum of count at each iteration
        """
        d = {} 
        l = 0
        res = 0
        for r in range(len(s)):
            if s[r] not in d:
                d[s[r]] = 0
            d[s[r]] += 1
            while len(d.keys()) > 1:
                d[s[l]] -= 1
                if d[s[l]] == 0 :
                    del d[s[l]]
                l += 1
            res += d[s[r]]
        return res 

        ################################## optimize the space complexigy to O(1)
        class Solution:
    def countLetters(self, s: str) -> int:
        l = 0
        res = 0
        for r in range(len(s)+1):
            if r == len(s) or s[l] != s[r]:
                len_substring = r-l
                res += (1+len_substring)*len_substring // 2 
                l = r 
        return res 

class Solution:
    def countLetters(self, s: str) -> int:
        """ tc O(N)  sc O(1)
        substring[i] = substring[i-1] +1   if s[i] == s[i-1] else 1 
        """
        cnt = 1
        total = 1 
        for i in range(1,len(s)):
            if s[i] == s[i-1]:
                cnt += 1
            else:
                cnt = 1 
            
            total += cnt 
        return total