Count Number of Homogenous Substrings

Code

MOD = 10**9 + 7
 
def countHomogenous(s):
    n = len(s)
    count = 0
    slow, fast = 0, 0
 
    while fast < n:
        if s[fast] != s[slow]:
            count += (fast - slow) * (fast - slow + 1) // 2
            count %= MOD
            slow = fast
        fast += 1
 
    count += (fast - slow) * (fast - slow + 1) // 2
    count %= MOD
 
    return count
 
# Test cases
s1 = "abbcccaa"
s2 = "xy"
s3 = "zzzzz"
print(countHomogenous(s1))  # Output: 13
print(countHomogenous(s2))  # Output: 2
print(countHomogenous(s3))  # Output: 15
 

Attempt 1

• If all characters of a string a same.
• Here Fast & Slow Pointers Algorithm can be used but how to decide the number, lets say if slow and fast pointer are same then +2 store this value and do +1 in that and then add that to the main sum?
• Q. When do you gettime_limit_exceeded error?
• TC: n
• Q. Why is remainder of count with MOD required?
• python_trick // is used to divide the number and round up to the nearest integer.

 
class Solution(object):
 
	def countHomogenous(self, s):
		slow_pointer = 0
		fast_pointer = 0
		sum = 0
		while fast_pointer < len(s) + 1:
			if s[slow_pointer] != s[fast_pointer]:
				sum += 1
				slow_pointer += 1
				fast_pointer += 1
			else:
				fast_pointer += 1
 
 
s = "abbcccaa"
sol = Solution().countHomogenous(s)
 

Links

• https://leetcode.com/problems/count-number-of-homogenous-substrings