Number of Substrings Containing All Three Characters

Share

Count substrings containing at least one of each: "a", "b", "c".

Example 1
Input: s="abcabc" → Output: 10
Example 2
Input: s="aaacb" → Output: 3

Solution Approach

For each right, track last seen position of a,b,c. Valid substrings end at right, start at 0..min(last[a],last[b],last[c]).

  • Track last seen index of a, b, c (init -1)
  • For each position: update last seen for current char
  • Count = min(last[a], last[b], last[c]) + 1 (all starting points that form valid window)
  • Add to total
Java
public int numberOfSubstrings(String s) {
    int[] last = {-1, -1, -1};
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
        count += 1 + Math.min(last[0], Math.min(last[1], last[2]));
    }
    return count;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)