Problem

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.

Examples

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^4
  • s only consists of a , b or _c _characters.

Solution

Method 1 - Sliding Window

To solve this problem, we can use the sliding window technique, which is efficient for this type of substring problem.

A substring containing all three characters starting at an index start and ending at index end will also contain all three characters if it ends at any index beyond end.

Approach

  1. Use a sliding window approach with two pointers (start and end) to traverse the string.
  2. Maintain a count of characters (‘a’, ‘b’, and ‘c’) in the current window using a frequency map or an array.
  3. Expand the window by moving the end pointer, adding characters to the count.
  4. Once the window contains at least one occurrence of ‘a’, ‘b’, and ‘c’, calculate the valid substrings ending at end. The count of these substrings is (n - end), where n is the length of the string. Move the start pointer to shrink the window and continue this process.
  5. Repeat until the window can no longer contain all three characters.

Code

Java
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        Map<Character, Integer> cnt = new HashMap<>();
        int start = 0, ans = 0;
        
        for (int end = 0; end < n; end++) {
            cnt.put(s.charAt(end), cnt.getOrDefault(s.charAt(end), 0) + 1);
            while (cnt.getOrDefault('a', 0) > 0 && 
                cnt.getOrDefault('b', 0) > 0 && 
                cnt.getOrDefault('c', 0) > 0) {
                ans += n - end;
                cnt.put(s.charAt(start), cnt.get(s.charAt(start)) - 1);
                start++;
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n: int = len(s)
        cnt: Counter = Counter()
        start: int = 0
        ans: int = 0
        
        for end, char in enumerate(s):
            cnt[char] += 1
            while all(c in cnt and cnt[c] > 0 for c in 'abc'):
                ans += n - end
                cnt[s[start]] -= 1
                start += 1
                
        return ans

Complexity

  • ⏰ Time complexity: O(n). Each character is processed at most twice — once when expanding the window with end and once when shrinking the window with start.
  • 🧺 Space complexity: O(1). Only a fixed-sized array or map is used to store the frequency of the characters.

Dry Run

Lets take eg1 - s = "abcabc".

  1. Initially, the window is [a] → invalid. Expand.
  2. Window becomes [a, b] → invalid. Expand.
  3. Window becomes [a, b, c] → valid. Compute substrings and move start.
    • Substrings ending at c: abc, abca, abcab, abcabc → count = 4.
  4. Shrink the window by moving start, repeat similar checks.

…

There are 10 substrings containing all three characters.