[LeetCode] 1358. Number of Substrings Containing All Three Characters (Python)

 

 

난이도: Medium

Problem Description

---

 

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.

 

 

Problem Example

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^4
• s only consists of a, b or c characters.

 

 

✏️ Solution

---

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        abc = {'a':0, 'b':0, 'c':0}
        n = len(s)
        left, cnt, answer = 0, 0, 0

        for right in range(n):
            abc[s[right]] += 1
            if abc[s[right]] == 1:
                cnt += 1
            
            if cnt == 3:
                while True:
                    answer += n - right
                    abc[s[left]] -= 1
                    if abc[s[left]] == 0:
                        left+=1
                        break
                    left += 1
                cnt -= 1

        return answer

 

Sliding Window 기법을 통해 해결했다.

 

먼저 right를 이동하며 각 문자의 등장 횟수를 기록했다.

 

이 때, 모든 문자가 한 번 이상 등장하면 left 포인터를 이동하며 가능한 부분 문자열 개수를 더했다.

 

left를 이동할 때 한 문자의 개수가 0이 되면 중단하고, cnt 값을 감소 시켜주었다.

 

이 과정을 문자열의 끝까지 반복하여 answer를 찾아갔다.

 

answer는 n-right값으로 더해 나갔다.

왜냐하면 이미 a,b,c를 모두 포함하는 부분 문자열이 있을 때 뒤에 뭐가 나와도 조건을 만족하기 때문이다.

 

예를 들어 s= abcabc이고 현재 left=0, right= 2라고 했을 때, 부분 문자열은 abc가 된다.

 

이 abc뒤에 무엇이와도 조건을 만족한다. 따라서 abca도 만족, abcab도 만족, abcabc도 만족하게 된다.

 

즉 현재 부분 문자열이 abc이면 abc, abca, abcab, abcabc 총 4개를 만족하는 것을 알 수 있다.

 

이는 s의 길이 6과 현재 right값 2를 빼주어 구할 수 있다 --> 6-2 = 4

 

이런식으로 조건을 만족하는 부분 문자열이 있을 때 효율적으로 계산할 수 있다.

 

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 1358. Number of Substrings Containing All Three Characters (Python)

 

깃허브: githb

algorithmPractice/LeetCode/1460-number-of-substrings-containing-all-three-characters at main · laewonJeong/algorithmPractice