Number of Substrings Containing All Three Characters [Medium]

Problem Statement

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

Input: "abcabc" → Output: 10

Intuition

For each right position, the leftmost valid left is min(last_a,last_b,last_c)+1. All substrings from [0..left-1..right] are valid → add min(last)+1.

Solutions

C++

int numberOfSubstrings(string s) {
    int last[3]={-1,-1,-1}, ans=0;
    for(int i=0;i<s.size();i++){
        last[s[i]-'a']=i;
        ans+=min({last[0],last[1],last[2]})+1;
    }
    return ans;
}

Java

public int numberOfSubstrings(String s) {
    int[] last={-1,-1,-1}; int ans=0;
    for(int i=0;i<s.length();i++){
        last[s.charAt(i)-'a']=i;
        ans+=Math.min(last[0],Math.min(last[1],last[2]))+1;
    }
    return ans;
}

Python

def numberOfSubstrings(s: str) -> int:
    last = {'a': -1, 'b': -1, 'c': -1}
    ans = 0
    for i, c in enumerate(s):
        last[c] = i
        ans += min(last.values()) + 1
    return ans

Complexity

Time: O(n), Space: O(1)