1358. Number of Substrings Containing All Three Characters
Problem Description
The given problem requires us to find the number of substrings in a string s
that contains at least one occurrence of the characters 'a', 'b', and 'c'. The string s
consists only of these three characters. A substring is any sequence of consecutive characters from the string. The goal is to count all such possible substrings where each of the three characters appears at least once.
Intuition
To solve this problem, we use a sliding window approach to track the latest positions of 'a', 'b', and 'c' while iterating through the string. The key intuition here is to understand that once we have found a substring containing all three characters, extending this substring to the right (by adding more characters in sequence) will also form valid substrings containing all three characters.
Hereās the step-by-step intuition:
-
Initialize a dictionary to store the latest index of 'a', 'b', and 'c'. By default, they are set to -1, indicating that they haven't been found yet.
-
Iterate through the string character by character, updating the dictionary with the new index of each character encountered.
-
At each step, determine the smallest of the three indices because the smallest index indicates the rightmost position up to which we have seen all three characters together.
-
For the current index
i
, the count of valid substrings ending ati
will be the minimum index among the latest indices of 'a', 'b', and 'c' plus one. This is because any substring starting from index 0 to the minimum index will have all three characters up to the current positioni
. -
Sum up all these counts to get the total number of substrings containing all three characters.
This simple yet elegant solution effectively counts all the necessary substrings by considering each valid end position and how many substrings it can generate based on the earlier occurrences of 'a', 'b', and 'c'.
Learn more about Sliding Window patterns.
Solution Approach
The solution approach uses the concept of pointers and a hash map (in Python, a dictionary) to efficiently keep track of the latest occurrence of each character 'a', 'b', and 'c'.
d = {"a": -1, "b": -1, "c": -1} # Dictionary to store the latest index for 'a', 'b', and 'c' ans = 0 # This will hold the total count of substrings
The dictionary d
serves as our hash map, holding the most recent indices of each character. Initially, all characters are set to -1
, indicating they have not been encountered yet.
Then, we start iterating over each character in the string:
for i, c in enumerate(s):
d[c] = i # Update the latest index for the character `c`
ans += min(d["a"], d["b"], d["c"]) + 1 # Count substrings ending at the current index `i`
As we iterate, for each character (c
) at index i
, we update its latest index in the dictionary. The min(d["a"], d["b"], d["c"])
finds the smallest index of the three, which, as previously mentioned, is the furthest right we can go while still having all three characters. By adding 1
to this minimum value, we get the number of substrings ending at index i
that has all three characters.
Finally, the sum of all such substrings is returned as the final answer:
return ans
Algorithm
-
Initialize a dictionary with keys 'a', 'b', 'c', and values
-1
. -
Start iterating over each character in the string using a
for
loop. -
Each time we find a character, update its latest index in the dictionary.
-
Calculate the number of valid substrings that end at the current index (minimum index of 'a', 'b', 'c' + 1).
-
Accumulate this count to a running total.
-
After the loop finishes, return the total count as the answer.
This algorithm is efficient because it processes each character exactly once and uses constant space for the dictionary, resulting in a time complexity of O(n) and a space complexity of O(1), where n is the length of the string.
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 use a string s = "abcabc"
to illustrate the solution approach.
- We start by initializing the dictionary
d
with{"a": -1, "b": -1, "c": -1}
. - Set our running total of valid substrings
ans
to0
.
Now we iterate through the string while keeping track of the latest index of each character in d
.
-
For
i = 0
(character = 'a'):- Update
d
to{"a": 0, "b": -1, "c": -1}
. - The minimum index among 'a', 'b', and 'c' is
-1
, soans += -1 + 1
, resulting inans = 0
.
- Update
-
For
i = 1
(character = 'b'):- Update
d
to{"a": 0, "b": 1, "c": -1}
. - The minimum index among 'a', 'b', and 'c' is still
-1
, soans += -1 + 1
, resulting inans = 0
.
- Update
-
For
i = 2
(character = 'c'):- Update
d
to{"a": 0, "b": 1, "c": 2}
. - Now we have all three characters, and the minimum index is
0
, soans += 0 + 1
, resulting inans = 1
.
- Update
-
For
i = 3
(character = 'a'):- Update
d
to{"a": 3, "b": 1, "c": 2}
. - The minimum index among 'a', 'b', and 'c' is now
1
, soans += 1 + 1
, resulting inans = 3
.
- Update
-
For
i = 4
(character = 'b'):- Update
d
to{"a": 3, "b": 4, "c": 2}
. - The minimum index among 'a', 'b', and 'c' is
2
, soans += 2 + 1
, resulting inans = 6
.
- Update
-
For
i = 5
(character = 'c'):- Update
d
to{"a": 3, "b": 4, "c": 5}
. - The minimum index among 'a', 'b', and 'c' is
3
, soans += 3 + 1
, resulting inans = 10
.
- Update
After the loop finishes, we return the total count, which is 10
.
Throughout this process, we efficiently tracked the latest positions of 'a', 'b', and 'c', calculated the substrings terminating at each character position, and accumulated this to find the total number of substrings containing all three characters.
Solution Implementation
1class Solution:
2 def numberOfSubstrings(self, string: str) -> int:
3 # Create a dictionary to keep track of the last seen index of 'a', 'b', and 'c'
4 last_seen_index = {"a": -1, "b": -1, "c": -1}
5 # Initialize answer to store the number of valid substrings
6 answer = 0
7 # Enumerate over the characters of the string
8 for index, char in enumerate(string):
9 # Update the last seen index for the current character
10 last_seen_index[char] = index
11 # Increment the answer by one more than the smallest last seen index among 'a', 'b', and 'c'
12 # This is because a valid substring must include at least one of each
13 answer += min(last_seen_index.values()) + 1
14
15 # Return the total count of valid substrings that contain at least one of each 'a', 'b', and 'c'
16 return answer
17
1class Solution {
2 public int numberOfSubstrings(String s) {
3 // Array to store the latest positions of characters 'a', 'b', and 'c'
4 int[] latestPosition = new int[] {-1, -1, -1};
5
6 // This will hold the count of valid substrings
7 int answer = 0;
8
9 // Iterate over each character in the string
10 for (int i = 0; i < s.length(); ++i) {
11 char currentChar = s.charAt(i);
12
13 // Update the latest position of the current character
14 latestPosition[currentChar - 'a'] = i;
15
16 // Find the smallest index among the latest positions of 'a', 'b', and 'c'
17 // and add 1 to get the count of valid substrings ending with the current character
18 int minPosition = Math.min(latestPosition[0], Math.min(latestPosition[1], latestPosition[2]));
19 answer += minPosition + 1;
20 }
21
22 return answer; // Return the total count of valid substrings
23 }
24}
25
1class Solution {
2public:
3 // Function to count the number of substrings containing all three characters 'a', 'b', and 'c'.
4 int numberOfSubstrings(string s) {
5 // Initialize an array to store the last seen positions of 'a', 'b', and 'c'.
6 int lastSeenPositions[3] = {-1, -1, -1};
7
8 // Initialize the answer to 0.
9 int substringCount = 0;
10
11 // Iterate over the string.
12 for (int index = 0; index < s.size(); ++index) {
13 // Update the last seen position for the current character.
14 lastSeenPositions[s[index] - 'a'] = index;
15
16 // Find the smallest index among the last seen positions of 'a', 'b', and 'c'.
17 // Add 1 because indices are 0-based, and we're interested in the number of elements.
18 int minLastSeenPosition = min(lastSeenPositions[0],
19 min(lastSeenPositions[1], lastSeenPositions[2])) + 1;
20
21 // Add the number of valid substrings ending with the current character.
22 // This is possible because any substring ending at the current index
23 // and starting before or at the smallest last seen index will contain all three characters.
24 substringCount += minLastSeenPosition;
25 }
26
27 // Return the total count of valid substrings.
28 return substringCount;
29 }
30};
31
1// Function to count the number of substrings containing all three characters 'a', 'b', and 'c'.
2function numberOfSubstrings(s: string): number {
3 // Initialize an array to store the last seen positions of 'a', 'b', and 'c'.
4 const lastSeenPositions: number[] = [-1, -1, -1];
5
6 // Initialize the answer to 0.
7 let substringCount: number = 0;
8
9 // Iterate over the string.
10 for (let index = 0; index < s.length; ++index) {
11 // Update the last seen position for the current character.
12 lastSeenPositions[s.charCodeAt(index) - 'a'.charCodeAt(0)] = index;
13
14 // Find the smallest index among the last seen positions of 'a', 'b', and 'c'.
15 const minLastSeenPosition: number = Math.min(lastSeenPositions[0],
16 Math.min(lastSeenPositions[1], lastSeenPositions[2])) + 1;
17
18 // Add the number of valid substrings ending with the current character.
19 // This is calculated by considering any substrings that end at the current index
20 // and start before or at the smallest last seen index, thus including all three characters.
21 substringCount += minLastSeenPosition;
22 }
23
24 // Return the total count of valid substrings.
25 return substringCount;
26}
27
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the string s
. This is because the code iterates over each character in the string exactly once. Within the loop, updating the dictionary and calculating the minimum value and the cumulative sum is done in constant time.
The space complexity of the code is O(1)
. The space is constant because the dictionary d
only stores three key-value pairs regardless of the size of the input string, corresponding to the characters 'a', 'b', and 'c'.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
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
Want a Structured Path to Master System Design Too? Donāt Miss This!