Number of Substrings Containing All Three Characters
Count substrings containing at least one a, b, and c — sliding window with `ans += left` trick.
Problem#
Given a string s made of a, b, c, count the substrings that contain at least one of each.
Examples#
"abcabc"→10"aaacb"→3
Constraints#
3 <= s.length <= 5 * 10^4.
Approach#
Walk right, track counts of each character. While all three are present, shrink left. For each right, count = left valid starting positions (every prefix [0..left-1] extended to right is valid).
Solution#
class Solution {public: int numberOfSubstrings(string s) { int cnt[3] = {0}; int left = 0, ans = 0; for (int right = 0; right < (int)s.size(); ++right) { ++cnt[s[right] - 'a']; while (cnt[0] && cnt[1] && cnt[2]) { --cnt[s[left++] - 'a']; } ans += left; } return ans; }};func numberOfSubstrings(s string) int { var cnt [3]int left, ans := 0, 0 for right := 0; right < len(s); right++ { cnt[s[right]-'a']++ for cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 { cnt[s[left]-'a']-- left++ } ans += left } return ans}class Solution: def numberOfSubstrings(self, s: str) -> int: cnt = [0, 0, 0] left = 0 ans = 0 for right, ch in enumerate(s): cnt[ord(ch) - ord('a')] += 1 while cnt[0] and cnt[1] and cnt[2]: cnt[ord(s[left]) - ord('a')] -= 1 left += 1 ans += left return ansfunction numberOfSubstrings(s) { const cnt = [0, 0, 0]; let left = 0, ans = 0; for (let right = 0; right < s.length; right++) { cnt[s.charCodeAt(right) - 97]++; while (cnt[0] && cnt[1] && cnt[2]) { cnt[s.charCodeAt(left) - 97]--; left++; } ans += left; } return ans;}class Solution { public int numberOfSubstrings(String s) { int[] cnt = new int[3]; int left = 0, ans = 0; for (int right = 0; right < s.length(); right++) { cnt[s.charAt(right) - 'a']++; while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) { cnt[s.charAt(left) - 'a']--; left++; } ans += left; } return ans; }}function numberOfSubstrings(s: string): number { const cnt: number[] = [0, 0, 0]; let left = 0, ans = 0; for (let right = 0; right < s.length; right++) { cnt[s.charCodeAt(right) - 97]++; while (cnt[0] && cnt[1] && cnt[2]) { cnt[s.charCodeAt(left) - 97]--; left++; } ans += left; } return ans;}Editorial#
Once right is fixed and the window first becomes valid, any extension to the left (start ≤ left - 1) is also valid — so ans += left counts all of them simultaneously. After the inner loop, left is the smallest start that would be valid for the next right - 1, but for right itself we need the invalid start positions count, which is exactly left (positions 0..left-1 are valid as starts when paired with this right).
Wait — re-check the off-by-one: after the while loop, left is the first index where the window [left..right] is not yet covering all three. The valid starts are [0..left-1], count = left. Confirmed.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#