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 <= s.length <= 5 x 10^4s only consists of a, b or c characters.The sliding window technique is useful in efficiently identifying substrings in a given string. We can maintain a window that keeps track of the number of 'a', 'b', and 'c' characters using a map or counter.
Once the window contains all three characters, we count the number of valid substrings ending at the window's right-end by all possible window left-end positions.
The function maintains a count of each 'a', 'b', and 'c' in the current window using a dictionary. It increments the window's right edge to include each character from the string. If the window contains all three characters, it increments the result by the number of possibilities with the right edge at the current position and then moves the left edge to try and find new valid windows. This process continues until all possible substrings are evaluated.
JavaScript
Java
C++
C
C#
Time Complexity: O(n) - We iterate over the string once.
Space Complexity: O(1) - Constant space is used for the character count.
This straightforward approach checks every possible substring in the string, counts occurrences of 'a', 'b', and 'c', and increments the count of valid substrings. While not optimal, this method verifies the correctness of the problem when considering small inputs or verifying edge cases.
The function generates all substrings from the given string. It uses a helper function to check if the substring contains all characters 'a', 'b', and 'c'. If it does, it contributes to the valid substring count. This approach involves iterating through all possible start and end indices of substrings.
JavaScript
Time Complexity: O(n^3) - Due to generation and verification of all possible substrings.
Space Complexity: O(1) - No additional space needed beyond input size.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) - We iterate over the string once. |
| Brute Force Approach | Time Complexity: O(n^3) - Due to generation and verification of all possible substrings. |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Number of Substrings Containing All Three Characters with our built-in code editor and test cases.
Practice on FleetCode