Facebook Pixel

1180. Count Substrings with Only One Distinct Letter 🔒

EasyMathString
Leetcode Link

Problem Description

Given a string s, you need to find and return the total number of substrings that contain only one distinct letter.

A substring is a contiguous sequence of characters within the string. For a substring to have only one distinct letter, all characters in that substring must be the same.

For example, if s = "aaaba":

  • Valid substrings with one distinct letter include: "a", "aa", "aaa", "a" (at position 3), "b", "a" (at position 4)
  • The substrings can be broken down as:
    • From the first three 'a's: "a", "a", "a", "aa", "aa", "aaa" (total of 6)
    • From the 'b': "b" (total of 1)
    • From the last 'a': "a" (total of 1)
  • Total count = 6 + 1 + 1 = 8

The solution uses a two-pointer approach where it identifies consecutive segments of identical characters. For each segment of length n, the number of possible substrings is calculated using the formula n * (n + 1) / 2, which represents all possible contiguous substrings within that segment.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key observation is that substrings with only one distinct letter must consist of consecutive identical characters. If we have a segment of consecutive identical characters, we need to count all possible substrings within that segment.

Consider a segment of identical characters of length n. How many substrings can we form from it?

  • We can have n substrings of length 1
  • We can have n-1 substrings of length 2
  • We can have n-2 substrings of length 3
  • And so on...
  • We can have 1 substring of length n

The total count is n + (n-1) + (n-2) + ... + 1, which equals n * (n + 1) / 2.

This leads us to think about breaking the problem down: instead of checking every possible substring in the string, we can identify consecutive segments of identical characters and calculate the contribution of each segment independently.

For example, if we have "aaabba", we can break it into three segments:

  • "aaa" of length 3 contributes 3 * 4 / 2 = 6 substrings
  • "bb" of length 2 contributes 2 * 3 / 2 = 3 substrings
  • "a" of length 1 contributes 1 * 2 / 2 = 1 substring

The two-pointer technique naturally fits this approach: we use one pointer to mark the start of a segment and another pointer to find where the segment ends (where the character changes). Once we identify a segment, we calculate its contribution and move to the next segment.

Learn more about Math patterns.

Solution Approach

We use a two-pointer approach to identify and count substrings with only one distinct letter.

The algorithm works as follows:

  1. Initialize variables: Set pointer i to 0 (start of current segment), and ans to 0 (to accumulate the total count).

  2. Outer loop: While i is within the string bounds:

    • Set pointer j equal to i to mark the beginning of the search for the segment's end.

  3. Inner loop: Move j to the right as long as s[j] == s[i]:

    • This finds all consecutive characters that are the same as s[i].
    • When the loop ends, j points to the first character different from s[i], or past the end of the string.

  4. Calculate contribution: The segment [i, j-1] contains identical characters with length j - i.

    • The number of substrings in this segment is (j - i) * (j - i + 1) / 2.
    • In the code, this is written as (1 + j - i) * (j - i) // 2 which is mathematically equivalent.
    • Add this count to ans.

  5. Move to next segment: Set i = j to start processing the next segment of identical characters.

  6. Return result: After processing all segments, return ans.

Example walkthrough with s = "aaaba":

  • First iteration: i=0, j moves from 0 to 3 (finds "aaa"), count = 3 * 4 / 2 = 6
  • Second iteration: i=3, j moves from 3 to 4 (finds "b"), count = 1 * 2 / 2 = 1
  • Third iteration: i=4, j moves from 4 to 5 (finds "a"), count = 1 * 2 / 2 = 1
  • Total = 6 + 1 + 1 = 8

The time complexity is O(n) where n is the length of the string, as each character is visited exactly once by both pointers. The space complexity is O(1) as we only use a constant amount of extra space.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with s = "aabbba":

Initial State:

  • i = 0 (start of current segment)
  • ans = 0 (total count)

Iteration 1: Finding first segment "aa"

  • i = 0, character is 'a'
  • j starts at 0 and moves right while s[j] == 'a'
  • j stops at position 2 (where 'b' begins)
  • Segment length = j - i = 2 - 0 = 2
  • Substrings from "aa": "a" (position 0), "a" (position 1), "aa"
  • Count = 2 * (2 + 1) / 2 = 3
  • ans = 0 + 3 = 3
  • Move i to j (i = 2)

Iteration 2: Finding second segment "bbb"

  • i = 2, character is 'b'
  • j starts at 2 and moves right while s[j] == 'b'
  • j stops at position 5 (where 'a' begins)
  • Segment length = j - i = 5 - 2 = 3
  • Substrings from "bbb": "b", "b", "b", "bb", "bb", "bbb"
  • Count = 3 * (3 + 1) / 2 = 6
  • ans = 3 + 6 = 9
  • Move i to j (i = 5)

Iteration 3: Finding third segment "a"

  • i = 5, character is 'a'
  • j starts at 5 and moves right while s[j] == 'a'
  • j stops at position 6 (end of string)
  • Segment length = j - i = 6 - 5 = 1
  • Substrings from "a": just "a"
  • Count = 1 * (1 + 1) / 2 = 1
  • ans = 9 + 1 = 10
  • Move i to j (i = 6)

Termination:

  • i = 6 which equals the string length, so we exit

Final Result: 10

The algorithm efficiently processes each character exactly once, grouping consecutive identical characters and calculating their substring contributions using the formula n * (n + 1) / 2.

Solution Implementation

1class Solution:
2    def countLetters(self, s: str) -> int:
3        """
4        Count the total number of substrings consisting of only one distinct letter.
5      
6        Args:
7            s: Input string containing lowercase letters
8          
9        Returns:
10            Total count of homogeneous substrings
11        """
12        n = len(s)
13        current_index = 0
14        total_count = 0
15      
16        # Process each group of consecutive identical characters
17        while current_index < n:
18            # Find the end of current group of identical characters
19            group_end = current_index
20            while group_end < n and s[group_end] == s[current_index]:
21                group_end += 1
22          
23            # Calculate number of substrings in this group
24            # For a group of length k, there are k*(k+1)/2 substrings
25            group_length = group_end - current_index
26            substrings_in_group = (1 + group_length) * group_length // 2
27            total_count += substrings_in_group
28          
29            # Move to the next group
30            current_index = group_end
31      
32        return total_count
33
1class Solution {
2    /**
3     * Counts the total number of substrings that consist of only one unique character.
4     * For each group of consecutive identical characters, calculates the number of 
5     * possible substrings using the formula: n * (n + 1) / 2, where n is the length
6     * of the group.
7     * 
8     * @param s the input string
9     * @return the total count of substrings with only one unique character
10     */
11    public int countLetters(String s) {
12        int totalCount = 0;
13        int stringLength = s.length();
14      
15        // Iterate through the string, processing groups of identical consecutive characters
16        for (int startIndex = 0; startIndex < stringLength;) {
17            // Find the end of the current group of identical characters
18            int endIndex = startIndex;
19            while (endIndex < stringLength && s.charAt(endIndex) == s.charAt(startIndex)) {
20                endIndex++;
21            }
22          
23            // Calculate the length of the current group
24            int groupLength = endIndex - startIndex;
25          
26            // Add the number of substrings for this group using the formula:
27            // For a group of length n, there are n*(n+1)/2 possible substrings
28            // Example: "aaa" has 3 + 2 + 1 = 6 substrings: "a", "a", "a", "aa", "aa", "aaa"
29            totalCount += (1 + groupLength) * groupLength / 2;
30          
31            // Move to the next group of characters
32            startIndex = endIndex;
33        }
34      
35        return totalCount;
36    }
37}
38
1class Solution {
2public:
3    int countLetters(string s) {
4        int totalCount = 0;
5        int n = s.size();
6      
7        // Iterate through the string, processing groups of identical consecutive characters
8        for (int i = 0; i < n;) {
9            // Find the end of the current group of identical characters
10            int j = i;
11            while (j < n && s[j] == s[i]) {
12                ++j;
13            }
14          
15            // Calculate the number of substrings for this group
16            // For a group of length k, there are k*(k+1)/2 substrings
17            // This is because we can choose any starting position (k choices)
18            // and any ending position >= starting position
19            int groupLength = j - i;
20            totalCount += (1 + groupLength) * groupLength / 2;
21          
22            // Move to the next group of characters
23            i = j;
24        }
25      
26        return totalCount;
27    }
28};
29
1/**
2 * Counts the total number of substrings where all characters are the same.
3 * For each group of consecutive identical characters, it counts all possible substrings.
4 * 
5 * @param s - The input string to analyze
6 * @returns The total count of homogeneous substrings
7 */
8function countLetters(s: string): number {
9    let totalCount = 0;
10    const stringLength = s.length;
11  
12    // Iterate through the string, processing groups of identical characters
13    for (let startIndex = 0; startIndex < stringLength; ) {
14        let currentIndex = startIndex;
15        let groupSubstringCount = 0;
16      
17        // Count consecutive identical characters starting from startIndex
18        while (currentIndex < stringLength && s[currentIndex] === s[startIndex]) {
19            currentIndex++;
20            // For a group of n identical characters, there are n*(n+1)/2 substrings
21            // We accumulate this by adding 1, 2, 3, ... as we extend the group
22            groupSubstringCount++;
23            totalCount += groupSubstringCount;
24        }
25      
26        // Move to the next group of characters
27        startIndex = currentIndex;
28    }
29  
30    return totalCount;
31}
32

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. Although there are nested while loops, each character in the string is visited exactly once. The outer while loop moves through groups of consecutive identical characters, and the inner while loop finds the end of each group. The pointer i jumps directly to j after processing each group, ensuring linear traversal.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables n, i, j, and ans, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Formula Calculation

Pitfall: When calculating (1 + group_length) * group_length // 2, the multiplication might cause integer overflow in languages with fixed integer sizes (like C++ or Java). For very long segments of identical characters, the intermediate multiplication result could exceed integer limits before the division.

Solution:

  • In Python, this isn't an issue due to arbitrary precision integers
  • For other languages, use long/64-bit integers or rearrange the formula: 
    # Instead of: (1 + group_length) * group_length // 2
# Use: group_length // 2 * (group_length + 1) + (group_length % 2) * ((group_length + 1) // 2)
  • Alternatively, accumulate the count incrementally rather than using the formula

2. Off-by-One Error in Pointer Movement

Pitfall: Incorrectly handling the inner loop boundary check or pointer update can lead to:

  • Missing the last character if group_end < n is written as group_end < n-1
  • Double-counting characters if setting current_index = group_end - 1 instead of current_index = group_end
  • Index out of bounds if checking s[group_end] without verifying group_end < n first

Solution:

# Correct approach - always check bounds before accessing
while group_end < n and s[group_end] == s[current_index]:
    group_end += 1
# group_end now points to first different character or past the string end
current_index = group_end  # Start next iteration from this position

3. Using Wrong Formula for Counting Substrings

Pitfall: Using incorrect formulas like group_length * group_length or 2^group_length - 1, which don't correctly count all contiguous substrings of a segment.

Solution: Remember that for a segment of length n:

  • There are n substrings of length 1
  • There are n-1 substrings of length 2
  • There are n-2 substrings of length 3
  • ...
  • There is 1 substring of length n
  • Total = n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2

4. Misunderstanding the Problem Requirements

Pitfall: Counting distinct substrings instead of total substrings. For example, in "aaa", counting just {"a", "aa", "aaa"} = 3 instead of all occurrences.

Solution: The problem asks for the total count, not unique substrings. Each position where a valid substring can start should be counted separately, even if the substring content is identical to another.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More