Abstract / Summary

Count how many substrings in a string have all the same character.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (200k+ submissions).

Typical patterns to solve this problem:

• Math
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution class provides a method countHomogenous that receives a string s and returns the total number of substrings consisting of a single repeated character. The result is given modulo 1 000 000 007 to keep the value within a 32-bit integer range. The implementation walks through the input once, maintaining a running count of consecutive identical characters and aggregates the contribution of each position to the final answer.

Key Steps

The algorithm begins by establishing the accumulator result that will hold the total count.

result = 0

Two auxiliary variables are introduced: prev stores the character seen in the previous iteration, and same records the length of the current run of identical characters. same is seeded with 1 because a single character always forms a homogenous substring of length 1.

prev = ""
same = 1

The core of the method is a for loop that iterates over each character c in the input string.

for c in s:

Inside the loop the code checks whether the current character matches the previous one.

if prev == c:
    same += 1
else:
    same = 1
    prev = c

When the characters match, the length of the current run (same) is extended by one. When they differ, a new run starts: same resets to 1 and prev is updated to the new character. Immediately after this conditional, the current value of same is added to result. This addition captures all homogenous substrings that end at the current position, because a run of length k contributes the series 1 + 2 + … + k, and the incremental addition of same at each step builds that series naturally.

result += same

After the loop finishes, the method returns the accumulated total reduced modulo 1 000 000 007.

return result % 1_000_000_007

Edge Cases Handled

The implementation gracefully processes an empty string. Since the loop body never executes, result remains 0 and the final modulo operation yields 0, which correctly represents the absence of any substrings.

When the input consists of a single character, the loop runs once. prev is initially empty, so the else branch executes, setting same to 1 and prev to that character. result receives the value 1, and the modulo step returns 1, reflecting the sole homogenous substring.

If the entire string is composed of the same character, the if branch is taken for every iteration after the first. same grows linearly with the index, and result accumulates the triangular number sequence, delivering the exact count of all possible homogenous substrings.

For strings with alternating characters (e.g., "abab"), the else branch triggers on each change, resetting same to 1 each time. Consequently, result increments by 1 for every character, correctly counting only the trivial length-1 substrings.

Performance Optimizations

The algorithm achieves its goal with a single linear pass over the input, avoiding any nested loops or auxiliary data structures. By maintaining only two scalar variables (same and prev) besides the accumulator, it operates with constant extra memory regardless of input size. The incremental addition of same to result eliminates the need for a separate summation step after the loop, thereby reducing overhead. Finally, applying the modulo operation only once at the end avoids repeated costly reductions during accumulation.

Imagine a long train made of colored blocks. Some blocks are red, some are blue, and some are green. This code looks at the train to figure out how many tiny, matching groups of blocks are hiding inside.

The computer starts at the very front of the train and looks at each block one by one. It keeps a special box to remember which color it just saw. When it sees a block that matches the one right before it, it knows a group is getting bigger. It adds a number to a pile to keep track of how many groups it found.

If the computer sees a block that is a different color, it knows a new group has started. It starts counting from one again for that new color. Every time it moves to a new block, it adds the current size of the group to the total pile. By the time it reaches the end of the train, it has counted every single possible group of matching blocks.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	C#	C	Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality