Leetcode 1358. Number of Substrings Containing All Three Characters

문제

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.

• 주어진 문자열 s는 소문자 a, b, c 로만 이루어져 있다.
• a, b, c를 모두 포함하는 부분문자열의 모든 갯수를 구하시오

예시

s = "abcabc"
- abc
- bca
- abca
- cab
- bcab
- abcab
- abc
- cabc
- bcabc
- abcabc

- 10개 있다.

제한

• $3 <= s.length <= 5 x 10^4$
• 문자열 s는 소문자 a, b, c 로만 이루어진다.

풀이

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        window = {
            'a': 0,
            'b': 0,
            'c': 0,
        }
        N = len(s)

        def approve():
            return window['a'] > 0 and window['b'] > 0 and window['c'] > 0

        left = 0
        ans = 0
        for right, char in enumerate(s):
            window[char] += 1
            while approve():
                ans += N - right
                window[s[left]] -= 1
                left += 1

        return ans

• 슬라이딩 윈도우를 이용한다.