1930. Unique Length-3 Palindromic Subsequences

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/?envType=daily-question&envId=2025-01-04

 

주어진 문자열 s에서 길이가 3이고 중복되지 않은 팰린드롬의 갯수를 구하는 문제였다.

 

나는 백트래킹을 통해서 길이가 3인 모든 문자열을 찾아 Set에 넣어 중복되지 않은 문자열들을 구했다. 
그 다음에, Set을 순회하며 해당 문자열이 팰린드롬인지 판단해주었다. 

예제는 통과했지만, s의 길이가 10만이기 때문에 백트래킹을 시도했을 때 당연히 시초가 터졌다.

 

시간복잡도를 O(nlogn), 혹은 O(n) 이하로 줄일 방법을 찾아야 했다.

 

정답 풀이)

class Solution {
    public int countPalindromicSubsequence(String s) {
        Set<Character> set = new HashSet<>();

        int ans = 0;

        // 1. 고유한 문자를 저장
        for (char c : s.toCharArray()) set.add(c);

        for (char c : set) {

            // 2. 문자의 처음 등장 인덱스와 마지막 인덱스를 정의
            int i = -1;
            int j = 0;

            for(int k = 0; k < s.length(); k++) {

                // 3. 고유한 문자가 s의 문자와 일치하는 경우, 인덱스 값들을 갱신
                if (c == s.charAt(k)) {

                    if (i == -1) {
                        i = k;
                    }
                    j = k;
                }
            }

            Set<Character> between = new HashSet<>();

            // 4. 해당 문자의 첫번째와 마지막 인덱스 사이에 있는 모든 문자를 저장한다,
            for(int k = i + 1; k < j; k++) {
                between.add(s.charAt(k));
            }

            // 5. 저장한 사이즈만큼 결과값에 더해준다
            ans += between.size();
        }
        return ans;
    }
}

 

 

s = "aabca" 일때를 예시로 들어서 한번 로직을 설명해보겠다. 노트에 적으면서 하니까 잘 이해가 됐다.

 

맨 처음에, set에 고유한 문자열을 저장하므로 set = [a,b,c] 이렇게 저장되어 있을 것이다.

 

그리고, set을 순회하며 String s의 문자열과 비교를 진행한다.

맨 처음 "a"를 확인하는데, a의 처음 등장 인덱스는 0이고, 마지막 인덱스는 4이다. 

 

a의 인덱스 사이에 있는 문자들을 다시 set에 저장해줘야 하는데, i+1 ~ j까지의 문자들을 넣어주면 된다.

따라서, between = [a,b,c]가 되고 해당 Set의 사이즈를 결과값에 더해준다.

 

b나 c같은 경우, 처음 인덱스와 마지막 인덱스가 동일하기 때문에 between에는 빈 문자열만 더해주게 된다.

결과값은 a일 때 계산한 set의 크기인 3이 된다.

시간 복잡도는 최악의 경우에도 26 * O(n)으로, 길이가 10만이여도 통과하게 된다!

팰린드롬을 구할 때 특정 문자열의 처음 등장한 인덱스와 마지막 인덱스를 구해서 그 사이에 있는 문자열들을 넣고, 길이를 더해주는 방식이 답을 안보고 떠올리기 힘들었다.