Problem Informations

• Problem Index: 1358
• Problem Link: Number of Substrings Containing All Three Characters
• Topics: Hash Table, String, Sliding Window

Problem Description

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters *a*, *b* and *c* are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters *a*, *b* and *c* are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

• $3 \leq s.\text{length} \leq 5 \times 10^4$
• $s$ only consists of a, b or c characters.

Intuition

The problem requires us to find the number of substrings in a given string s containing at least one occurrence of each character ‘a’, ‘b’, and ‘c’. The complexity arises from ensuring that each substring contains all three characters, which requires carefully tracking their occurrences. An efficient way to approach this problem is by leveraging the sliding window technique alongside tracking the most recent occurrences of ‘a’, ‘b’, and ‘c’ as we iterate through the string.

Approach

The solution utilizes a single pass traversal of the string s with a focus on maintaining the most recent indices for each of the characters ‘a’, ‘b’, and ‘c’. Here’s a detailed breakdown of the approach:

1. Initialization: We start by initializing a result variable result to zero, which will ultimately store the number of valid substrings. Additionally, we maintain a vector last_seen_index initialized to {-1, -1, -1}. This vector tracks the last seen index of ‘a’, ‘b’, and ‘c’ respectively.

2. Traversal: As we iterate over each character in the string s, we perform the following:

   • Update the last_seen_index for the current character. This is achieved by transforming the character into an index using s[i] - 'a', which computes to 0 for ‘a’, 1 for ‘b’, and 2 for ‘c’, and assigns the current index i to the respective position in the last_seen_index vector.

3. Determine Valid Substrings: At each index i:

   • Compute the minimum value in last_seen_index using min_element, representing the earliest index of the last recorded positions of ‘a’, ‘b’, and ‘c’.
   • If this minimum value is not -1, it indicates all characters (‘a’, ‘b’, ‘c’) have been encountered at least once up to the current index. The number of valid substrings ending at i will therefore be min_index + 1. This is because any substring starting from index 0 to min_index and ending at i will include at least one occurrence of ‘a’, ‘b’, and ‘c’.

4. Update Result: Add the number computed in the previous step to result.

5. Return Result: After exiting the loop, the result variable holds the total number of substrings satisfying the condition, which is returned as the final output.

This approach ensures that we efficiently find all valid substrings in a single pass over the string with a time complexity of $O(n)$, where $n$ is the length of the string s.

Code

C++

class Solution {
public:
    int numberOfSubstrings(string s) {
        int result = 0;  // Variable to store the number of valid substrings
        vector<int> last_seen_index = {-1, -1, -1};  // Array to track the last seen index of 'a', 'b', and 'c'
        
        for (int i = 0; i < s.size(); i++) {
            // Update the last seen index for the current character
            last_seen_index[s[i] - 'a'] = i; 
            
            // Find the minimum index among the last seen indices of 'a', 'b', and 'c'
            int min_index = *min_element(last_seen_index.begin(), last_seen_index.end());
            
            // If all characters 'a', 'b', and 'c' have been seen at least once, update result
            if (min_index != -1) {
                result += min_index + 1;
            }
        }
        
        return result;  // Return the total number of valid substrings
    }
};

Python

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        result = 0  # Variable to store the number of valid substrings
        last_seen_index = [-1, -1, -1]  # Array to track the last seen index of 'a', 'b', and 'c'
        
        for i in range(len(s)):
            # Update the last seen index for the current character
            last_seen_index[ord(s[i]) - ord('a')] = i 
            
            # Find the minimum index among the last seen indices of 'a', 'b', and 'c'
            min_index = min(last_seen_index)
            
            # If all characters 'a', 'b', and 'c' have been seen at least once, update result
            if min_index != -1:
                result += min_index + 1
        
        return result  # Return the total number of valid substrings

Complexity

• Time complexity: $O(n)$
  The time complexity is $O(n)$ because we traverse the string s exactly once in the for loop. For each character in the string, we update the last_seen_index array and compute the min_index using the min_element function, both of which are constant time operations $O(1)$. Thus, the overall time complexity is linear with respect to the length of the string.
• Space complexity: $O(1)$
  The space complexity is $O(1)$ because we use a fixed amount of additional storage. The last_seen_index array has a constant size of 3, independent of the input size, and constant space is used for other variables. Therefore, the space complexity is constant.