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^4sonly consists of a, b or c characters.
Solution
Record the last index of each character.
At each index i, we can choose any index j that j <= min(last_a, last_b, last_c) as the starting point, and there will be min(last_a, last_b, last_c) + 1 valid substrings.
e.g. aabbabcc…
last_a = 4
last_b = 5
last_c = 7
min(last_a, last_b, last_c) = 4
aabba | bcc
We can choose any char with index <= 4 as string point, there are 5 of them:
aabbabcc
abbabcc
bbabcc
babcc
abcc
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int numberOfSubstrings(string s) { vector<int> l{-1,-1,-1}; int ans = 0; for (size_t i = 0; i < s.length(); ++i) { l[s[i] - 'a'] = i; ans += 1 + *min_element(begin(l), end(l)); } return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 |
# Author: Huahua class Solution: def numberOfSubstrings(self, s: str) -> int: l = {'a':-1, 'b':-1, 'c':-1} ans = 0 for i, ch in enumerate(s): l[ch] = i ans += min(l.values()) + 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment