Number of Substrings Containing All Three Characters

Share

Given a string s containing only characters a, b, c, return the number of substrings containing at least one occurrence of all three characters.

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

Solution Approach

Sliding window: for each right, maintain the last seen position of a, b, c. When all three are seen, all substrings ending at right and starting from 0 to min(last_a, last_b, last_c) are valid.

  • Track last[] = last index seen for each of a, b, c.
  • For each right, update last[s[right]-a] = right.
  • If all three have been seen: count += min(last[a], last[b], last[c]) + 1.
  • This is because we can choose any left from 0 to min(last positions).
Java
class Solution {
    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;
            if (last[0] >= 0 && last[1] >= 0 && last[2] >= 0)
                count += 1 + Math.min(last[0], Math.min(last[1], last[2]));
        }
        return count;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)