Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo $10^9 + 7$. A string is homogenous if all the characters of the string are the same. A substring is a contiguous sequence of characters within a string. Example 1 Input: s = "abbcccaa" Output: 13 Explanation: The homogenous substrings are listed as below: "a" appears 3 times. "aa" appears 1 time. "b" appears 2 times. "bb" appears 1 time. "c" appears 3 times. "cc" appears 2 times. "ccc" appears 1 time. 3 + 1 + 2 + 1 + 3 + 2 + 1 = 13. Example 2 Input: s = "ab" Output: 2 Explanation: The homogenous substrings are "a" and "b". Example 3 Input: s = "aaaaa" Output: 15 Constraints 1

Every homogenous substring is completely contained inside a run of identical characters. If a run has length L, the number of distinct substrings you can make inside that run is \begin{equation} 1+2+...+L = \frac{L(L+1)}{2} \end{equation} So the task reduces to Sweep through s, grouping consecutive equal characters. For each group of length L, add L*(L+1)//2 to the answer. Take the sum modulo MOD = 1 000 000 007. That’s O(n) time and O(1) extra space. In plain language: Time = O(n) Imagine you have a row of n blocks and you need to tap every single block once. The tapping time grows exactly with the number of blocks: double the blocks → double the taps. That’s all “O(n) time” means: the work the program does is directly proportional to the length of the input string. Space = O(1) While tapping those blocks you keep just a tiny counter in your hand, no matter whether there are 10 blocks or 10 million. That’s “O(1) space”: the extra memory the program needs stays the same size, just a few variables, no matter how big the string gets. def count_homogenous(s: str) -> int: M = 1_000_000_007 s = s.lower() # lower case only if len(s) > 100_000: raise ValueError("String too long") ans = 0 curr = 0 for i, ch in enumerate(s): if i and ch == s[i-1]: curr += 1 else: curr = 1 ans += curr if ans >= M: ans -= M return ans

Complete Training For Your Trading Interview

Interview Questions Programming Count Number of Homogenous Substrings

Unlock

Sorry, you don't have access to this interview question. Sign up to practice with our wide range of interview questions or use the filters to find free examples!

Related Questions

Title	Category	Subcategory	Difficulty	Status
All Vowels	Programming	String Manipulation	Easy	Unlock
Common Prefix Algorithm	Programming	String Manipulation	Medium	Unlock
Consecutive Letters	Programming	String Manipulation	Medium	Unlock
Group Anagrams	Programming	String Manipulation	Medium	Unlock
Palindrome Checker	Programming	String Manipulation	Medium	Unlock
Smallest String	Programming	String Manipulation	Easy	Unlock
Summing Up Strings #1	Programming	String Manipulation	Hard	Unlock
Summing Up Strings #2	Programming	String Manipulation	Hard	Unlock
Word Frequency	Programming	String Manipulation	Easy	Unlock
Words in a String	Programming	String Manipulation	Medium	Unlock

Discussion

Please log in to see the discussion.

Back to all Questions

The Interview Guide for Quants and Traders

Count Number of Homogenous Substrings

What do you think of this page?