Count Substrings with Only One Distinct Letter

Count Substrings with Only One Distinct Letter

What is this problem about?

The Count Substrings with Only One Distinct Letter coding problem asks you to find the total number of substrings within a given string that consist of only one unique character. For example, in the string "aaa", the valid substrings are "a" (three times), "aa" (twice), and "aaa" (once), totaling 6.

This is a classic problem of identifying contiguous blocks of identical characters and calculating how many smaller pieces can be carved out of them.

Why is this asked in interviews?

Companies like Virtu Financial use this question to test a candidate's ability to apply mathematical shortcuts to string processing. While you could generate all substrings and check them individually, doing so would be highly inefficient. This problem evaluates whether you can recognize the math interview pattern relating to triangular numbers and apply it to a string interview pattern task.

Algorithmic pattern used

This problem is solved using Linear Scan and Combinatorics.

1. Iterate through the string to find consecutive groups of the same character.
2. For a group of length $L$, the number of substrings that can be formed using only those characters is the sum of integers from 1 to $L$.
3. The formula for this sum is: $\frac{L imes (L + 1)}{2}$.
4. Sum these results for all groups in the string.

Example explanation

s = "aabbb"

1. Group 1: "aa" (Length $L=2$). Substrings: $\frac{2 imes (2+1)}{2} = 3$.
2. Group 2: "bbb" (Length $L=3$). Substrings: $\frac{3 imes (3+1)}{2} = 6$. Total = $3 + 6 = 9$.

The substrings for "aa" are s[0], s[1], and s[0..1]. The substrings for "bbb" are s[2], s[3], s[4], s[2..3], s[3..4], and s[2..4].

Common mistakes candidates make

• Generating all substrings: Attempting to use two nested loops to create every possible substring ($O(N^2)$), which is slow for large inputs.
• Off-by-one errors: Incorrectly calculating the length of the consecutive groups.
• Forgetting the last group: Failing to process the final group of characters after the loop finishes.

Interview preparation tip

Whenever you encounter a problem involving "consecutive identical elements," think about grouping them into counts first. Many subarray and substring problems become trivial math problems once you know the lengths of these uniform blocks.