1180. Count Substrings with Only One Distinct Letter
Problem Description
The problem requires counting the substrings within a given string s
that meet a specific criterion: each substring must contain exactly one distinct letter. In other words, any given substring is a sequence of the same character, with no other different characters inside. To illustrate, if s
is "aaa", we should count the individual substrings "a", "a", "a", the pairs "aa", "aa", and the entire string "aaa", which gives us a total of 6 such substrings.
Intuition
To solve this problem, we can observe patterns in the strings and how substrings forming consecutive identical characters contribute to the total count. Consider a substring with n
identical characters; it will have 1 + 2 + 3 + ... + n
distinct substrings with one distinct letter, which is the sum of the first n
natural numbers. We can use the formula for this sum, n * (n + 1) / 2
, to find the number of valid substrings in a piece of the sequence without the need for an exhaustive search for all possible substrings.
With this knowledge, we can look for these consecutive substrings of identical characters. We iterate through the string with two pointers (or indices) i
and j
. We use i
to start at the beginning of a substring with identical characters and j
to find its end. For each substring we find, we calculate its contribution to the total count using our sum formula and add it to ans
, which keeps track of the number of valid substrings. We repeat this process until we've considered every character in the string, at which point ans
will contain the final count of substrings with one distinct letter.
Learn more about Math patterns.
Solution Approach
The solution utilizes a simple iterative approach with two pointers to traverse the string efficiently. The key idea is to find consecutive groups of the same character and then calculate the number of substrings that can be formed from these groups using a mathematical formula. This eliminates the need for nested loops to consider every possible substring explicitly. We'll break down the steps of the implementation:
- Initialize two pointers,
i
andj
.i
will scan through the string, andj
will be used to find the end of a consecutive group of identical characters starting ati
. - Initialize
ans
to zero, which will be used to accumulate the total number of substrings with one distinct letter. - Use a
while
loop to iterate over the string with the conditioni < n
, ensuring we don't go past the string's end. - Within the loop, set
j
toi
to mark the beginning of the new possible consecutive group. - Start a nested
while
loop to movej
forward as long asj < n
ands[j]
is equal tos[i]
. This loop determines the length of the consecutive group. - With the length of the consecutive group determined (
j - i
), calculate the number of substrings using the formula(1 + j - i) * (j - i) // 2
. This formula represents the sum of the firstj - i
natural numbers. - Add this calculated number to
ans
, accumulating the count of valid substrings. - Update
i
toj
to move the first pointer to the next group of identical characters. - Return
ans
once the entire string has been scanned.
The algorithm makes a single pass over the string, achieving linear time complexity, O(n), where n is the length of the input string. The space complexity is O(1) as it only uses a constant amount of extra space for the pointers and counter. This efficiency stems from the combination of the two pointers technique and the application of the arithmetic series sum formula.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach using the string s = "aabbbc"
as an example.
Following the steps:
-
Initialize two pointers,
i
andj
. We start by setting bothi = 0
andj = 0
. -
Initialize
ans
to zero. This will hold the count of valid substrings. So,ans = 0
. -
Use a
while
loop to iterate over the string. Sincei < n
wheren = 6
(length of "aabbbc"), the loop begins. -
Within the loop, set
j = i
. This acknowledges the start of a new consecutive group (we expectj
to find how long it goes). -
Start a nested
while
loop withj < n
ands[j] == s[i]
.- For
i = 0
,j
moves from0
to1
ass[0]
(which is 'a') is the same ass[1]
.j
stops at2
becauses[2]
is different ('b'). - The group "aa" ends at index
1
, thus with lengthj - i = 2
.
- For
-
Calculate the number of substrings:
(1 + j - i) * (j - i) // 2 = (1 + 2 - 0) * (2 - 0) // 2 = 3 * 2 // 2 = 3
. -
Add to
ans
:ans = ans + 3
which becomesans = 3
. -
Update
i
toj
: seti
to2
wherej
had stopped.
Now we continue the steps for the next group of identical characters 'b':
-
While loop continues with
i = 2
. As before, we setj = i
. -
Nested
while
loop identifies the group "bbb": The loop starts atj = 2
and incrementsj
until it reaches5
, right before 'c', as 'b's are consecutive until index4
. -
Calculate for "bbb":
(1 + j - i) * (j - i) // 2 = (1 + 5 - 2) * (5 - 2) // 2 = 4 * 3 // 2 = 6
. -
Add to
ans
:ans = ans + 6
which now becomesans = 9
. -
Update
i
to the new positionj = 5
, skipping over the 'bbb' group.
The loop won't find any more groups longer than 1 character ('c' is a single character).
-
Remaining single character will be the group "c":
- Since
j == n
and no further groups are possible, we simply add1
for the solo 'c'. ans = ans + 1
which now becomesans = 10
.
- Since
The string has been fully scanned:
- Return
ans
. The final count of substrings where each contains exactly one distinct letter is10
.
We've just applied the solution approach using two-pointer technique to efficiently calculate the number of substrings within the string "aabbbc" that consist of the same character. The total count of valid substrings in this case is 10
, which is the sum of substrings from groups "aa", "bbb", and "c".
Solution Implementation
1class Solution:
2 def countLetters(self, s: str) -> int:
3 # Initialize the length of the string for easy reference
4 string_length = len(s)
5
6 # Initialize the index and answer variables
7 index, total_count = 0, 0
8
9 # Iterate over the string, using 'index' as the starting pointer
10 while index < string_length:
11 # Set 'current_char' as the character at the current index
12 current_char = s[index]
13 # Initialize 'span_length' which will count the span of identical characters
14 span_length = 0
15
16 # Count continuous span of identical characters starting from 'index'
17 while index < string_length and s[index] == current_char:
18 span_length += 1
19 index += 1
20
21 # Calculate the total substrings for the span and add to 'total_count'
22 # The formula (span_length * (span_length + 1)) // 2 calculates the number of total
23 # possible substrings in a string containing identical characters.
24 total_count += (span_length * (span_length + 1)) // 2
25
26 # Return the total count of all possible substrings
27 return total_count
28
1class Solution {
2
3 // This method counts all possible substrings which consist of the same character
4 public int countLetters(String s) {
5 int totalCount = 0; // Initialize total count of valid substrings
6
7 // Iterate through the string starting from the first character
8 for (int currentIndex = 0, stringLength = s.length(); currentIndex < stringLength;) {
9 int nextIndex = currentIndex; // Index to find the end of a group of identical characters
10 // Continue while we have the same character as at currentIndex
11 while (nextIndex < stringLength && s.charAt(nextIndex) == s.charAt(currentIndex)) {
12 nextIndex++;
13 }
14
15 // Calculate the number of substrings that can be formed with the same character
16 // and add it to totalCount. It is based on the arithmetic series (n(n+1)/2).
17 int sameCharCount = nextIndex - currentIndex;
18 totalCount += (sameCharCount + 1) * sameCharCount / 2;
19
20 // Skip to the next character group
21 currentIndex = nextIndex;
22 }
23
24 // Return the total count of substrings
25 return totalCount;
26 }
27}
28
1class Solution {
2public:
3 // Function to count the total number of substrings that have all the same letters
4 int countLetters(string s) {
5 int totalCount = 0; // This will hold the final count of substrings
6 int n = s.size(); // Get the size of the string to iterate over
7
8 // Loop through the string
9 for (int i = 0; i < n;) {
10 // Start of the current substring with the same character
11 int start = i;
12
13 // Find the end of the current group of the same character
14 while (i < n && s[i] == s[start]) {
15 ++i;
16 }
17
18 // Length of the group of the same character
19 int length = i - start;
20
21 // Add the count of substrings for this group to totalCount
22 // Counts the number of substrings that can be formed with 'length' characters,
23 // which is the sum of the series 1 + 2 + ... + length.
24 totalCount += (1 + length) * length / 2;
25
26 // No need to set i = j, as i is already at the end of the current character group
27 }
28
29 return totalCount; // Return the total count of all such substrings
30 }
31};
32
1/**
2 * Counts the total number of contiguous occurrences of each letter
3 * in the string `s`. For each continuous group of the same character,
4 * it adds up a series, where the nth character contributes n to the count
5 * (e.g., for "aa" it adds 1 for the first 'a' and 2 for the second 'a', giving 3).
6 *
7 * @param {string} s - The string to analyze.
8 * @return {number} - The total count of contiguous letters.
9 */
10function countLetters(s: string): number {
11 let totalCount = 0; // Initialize total count
12 const lengthOfS = s.length; // Cache the length of the string
13
14 // Iterate over the string
15 for (let index = 0; index < lengthOfS; ) {
16 let currentIndex = index; // Index used to find contiguous characters
17 let contiguousCount = 0; // Reset counter for contiguous characters
18
19 // Count contiguous occurrences of the character
20 while (currentIndex < lengthOfS && s[currentIndex] === s[index]) {
21 ++currentIndex; // Move to the next character
22 totalCount += ++contiguousCount; // Increment and add to total count
23 }
24
25 // Continue from where the last contiguous sequence ended
26 index = currentIndex;
27 }
28
29 return totalCount; // Return the computed total count
30}
31
Time and Space Complexity
Time Complexity
The given Python code for countLetters
has two nested loops. However, the inner loop does not start from the beginning every time, but rather from the index where the outer loop left off. The inner loop only runs when it finds characters in string s
that are the same as the character at index i
, and once it finds a different character, it breaks and sets i
to j
(the next start position). This means each character in the string is visited exactly once by the inner loop, and thus the total number of iterations across both loops is O(n)
, where n
is the length of the string s
.
Therefore, time complexity is O(n)
.
Space Complexity
As for the space complexity, the code uses a fixed number of integer variables (n
, i
, j
, ans
) that do not depend on the size of the input string s
. No additional data structures are used that would grow with the input size.
Therefore, space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
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
LeetCode 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 we
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.