Count Substrings with Only One Distinct Letter - Video Solutions

Problem Overview: Given a string s, count how many substrings contain only one distinct character. Any substring made entirely of the same letter is valid. For example, the run "aaa" contributes a, a, a, aa, aa, and aaa.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Generate every substring starting at index i. Extend the substring to the right while checking if all characters match the first character. The moment a different character appears, stop expanding that start index. Each valid extension contributes one substring to the answer. This approach directly models the problem but still checks up to n extensions for each index, resulting in O(n²) time. Useful for understanding the structure of valid substrings but inefficient for large strings.

Approach 2: Consecutive Run Counting (Math Insight) (O(n) time, O(1) space)

Instead of checking every substring, group consecutive identical characters. If a character repeats k times in a row, the number of valid substrings formed from that run is k * (k + 1) / 2. For example, the run "bbbb" produces 4 + 3 + 2 + 1 = 10 substrings. Iterate through the string, track the length of the current run, and add the formula when the run ends. This converts the problem into simple counting and uses basic math combined with linear scanning of the string.

Approach 3: Two Pointers / Sliding Window (O(n) time, O(1) space)

Use two pointers to maintain a window where all characters are identical. Start both pointers at the beginning. Move the right pointer forward while the character matches the left pointer’s character. Each extension adds (right - left + 1) new valid substrings ending at right. When the character changes, reset the left pointer to the new position. This is essentially a two pointers version of run counting and works well when you naturally think in terms of sliding windows.

Recommended for interviews: The consecutive run counting approach is the cleanest solution. It demonstrates that you recognize the combinatorial pattern in repeated characters and reduces the problem to a single linear scan. Starting with the brute force explanation shows understanding of the problem space, but interviewers expect the O(n) run-based or two-pointer optimization.