0. 문제

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

1. 초기 코드

$시간복잡도= O(N^2)$

문제점

코드 구성 논리는 문제없지만, 시간복잡도가 너무 높음.

class Solution {
    public static int numberOfSubstrings(String s) {
        int count = 0;
        boolean a = false;
        boolean b = false;
        boolean c = false;

        for (int i = 0; i < s.length(); i++) {
            a = false;
            b = false;
            c = false;
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(j) == 'a')
                    a = true;
                if (s.charAt(j) == 'b')
                    b = true;
                if (s.charAt(j) == 'c')
                    c = true;
                if (a && b && c) {
                    count += s.length() - j;
                    break;
                }
            }
        }
        if (s.length() > 2)
            return count; //+ numberOfSubstrings(s.substring(1));
        else
            return 0;
    }
}

2. 정답 코드

$시간복잡도=O(N)$

Sliding Window(Two Pointer) 활용해 시간복잡도 최적화.

Sliding Window?

• 문자열 한 번만 순회하면서 조건 만족하는 구간을 빠르게 탐색. 이중 반복문을 피할 수 있음.
• 일반적으로 포인터 2개 (left, right)를 통해 윈도우의 크기를 동적으로 조정함. 윈도우 크기를 동적으로 조절하는 것이 핵심 포인트.
• 이 코드의 경우 명시적인 left는 없지만, lastSeen을 통해 윈도우를 능동적으로 변화시킴.

// right만 사용한 경우
class Solution {
    public static int numberOfSubstrings(String s) {
        int count = 0;
        int[] lastSeen = {-1, -1, -1};

        for (int i = 0; i < s.length(); i++) {
            lastSeen[s.charAt(i) - 'a'] = i;

            if (lastSeen[0] != -1 && lastSeen[1] != -1 && lastSeen[2] != -1) {
                minIndex= count + Math.min(lastSeen[0], Math.min(lastSeen[1], lastSeen[2]));
                count += minIndex + 1;
            }
        }
        return count;
    }
}

// left도 적용한 경우
class Solution {
    public static int numberOfSubstrings(String s) {
        int count = 0;
        int[] freq = {0, 0, 0};  // 'a', 'b', 'c' 등장 횟수
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            freq[s.charAt(right) - 'a']++;  // 현재 문자의 개수 추가

            // 'a', 'b', 'c'가 모두 포함되면 left를 이동
            while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
                count += s.length() - right;  // 남은 길이 더하기
                freq[s.charAt(left) - 'a']--;  // left 이동 후 감소
                left++;
            }
        }
        return count;
    }
}