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.
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^4s only consists of a, b or c characters.class Solution {
public int numberOfSubstrings(String s) {
int n = s.length(), lt = 0, rt = 0, ans = 0;
int[] freq = new int[3];
while (rt < n) {
freq[s.charAt(rt) - 'a']++;
while (valid(freq)) {
ans += n - rt;
freq[s.charAt(lt++) - 'a']--;
}
rt++;
}
return ans;
}
boolean valid(int[] freq) {
return freq[0] > 0 && freq[1] > 0 && freq[2] > 0;
}
}class Solution {
public int numberOfSubstrings(String s) {
int n = s.length(), lt = 0, rt = 0, ans = 0;
int[] lastPosn = new int[3];
Arrays.fill(lastPosn, -1);
while (rt < n) {
lastPosn[s.charAt(rt) - 'a'] = rt++;
ans += 1 + Math.min(Math.min(lastPosn[0], lastPosn[1]), lastPosn[2]);
}
return ans;
}
}