Count Number of Homogenous Substrings

Problem Id: 1759 Difficulty: Medium Tag: String Tag: Greedy


Intuition

For any character in the string, the number of substrings that ends with it equals to the number of same characters.

For example, ....ac, in this case, number of substrings ends with this c is 1. And ....acc, in this case, number of substrings ends with this c is 2.

Solution


class Solution:
    def countHomogenous(self, s):
        prev = None
        count = 0
        num_homo = 0
        for c in s:
            if c != prev:
                count = 1
                prev = c
            else:
                count += 1
            num_homo += count
        return num_homo % (10 ** 9 + 7)