LeetCode - 1358. Number of Substrings Containing All Three Characters

문제링크

 

문제 설명

문자열 s가 주어집니다. s는 오직 문자 'a', 'b', 'c'로만 이루어져 있습니다.

최소 한 번 이상 'a', 'b', 'c'가 모두 포함된 부분 문자열(substring) 의 개수를 반환하세요.

제한 사항

• 3 <= s.length <= 5 x 10^4
• s only consists of a, b or c characters.

예시

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

풀이 흐름

• 처음에는 백트래킹으로 접근했지만 s의 길이로 인해 백트래킹으로 접근하면 시간초과가 발생합니다.
• 그 다음에는 s는 a, b, c로만 이루어져 있으니 배열을 이용해 해당 정보를 저장할 수 있지 않을까 생각했습니다.
• 부분 문자열의 갯수를 세기 위한 방법으로 a, b, c가 가장 마지막으로 나온 인덱스를 저장한 뒤 각 값 중 가장 작은 값에 1을 더한 값이 부분 문자열의 갯수가 된다는 사실을 파악했습니다.
  • 예시) 문자열이 'abcabc' 인 경우(i는 인덱스, tmp는 각 문자가 등장한 마지막 인덱스 만약 {2, 3, 1} 인 경우 a는 2번 인덱스, b는 3번 인덱스, c는 1번 인덱스에서 마지막으로 등장했다는 것을 의미)
  • i가 2일 때('abc' 까지 탐색했을 때) tmp는 {0, 1, 2} 가 되고 여기서 부분 문자열의 개수는 'abc' 1개 입니다.
    • Math.min(0, 1, 2) + 1 = 1
  • i가 3일 때('abca' 까지 탐색했을 때) tmp는 {3, 1, 2} 가 되고 여기서 부분 문자열의 개수는 i가 2일 때의 부분 문자열을 제외하면 'abca', 'bca' 2개 입니다.
    • Math.min(3, 1, 2) + 1 = 2
  • i가 4일 때('abcab' 까지 탐색했을 때) tmp는 {3, 4, 2} 가 되고 여기서 부분 문자열의 개수는 앞에서 발견한 부분 문자열의 개수를 제외하면 'abcab', 'bcab', 'cab' 3개 입니다.
    • Math.min(3, 4, 2) + 1 = 3
  • i가 5일 때('abcabc' 까지 탐색했을 때) tmp는 {3, 4, 5} 가 되고 여기서 부분 문자열의 개수는 앞에서 발견한 부분 문자열의 개수를 제외하면 'abcabc', 'bcabc', 'cabc', 'abc' 4개 입니다.
    • Math.min(3, 4, 5) + 1 = 4

코드

import java.util.*;

class Solution {
    public int numberOfSubstrings(String s) {
        int[] tmp = new int[3];
        Arrays.fill(tmp, -1);
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            tmp[s.charAt(i) - 'a'] = i;
            ans += Math.min(tmp[0], Math.min(tmp[1], tmp[2])) + 1;
        }
        return ans;
    }
}