[PS] Unique Length-3 Palindromic Subsequences

(바로 풀이가 나오므로 문제를 풀어보실 분은 주의가 필요합니다.)

해당 문제는 LeetCode의 Daily Question에서 2025.11.21.에 나온 문제입니다.
(난이도: Medium)

참신한 풀이가 있어서 가져왔습니다.

문제

문제 정의는 간단하게 서술하겠습니다. (자세한 건 위의 링크를 타고 들어가주세요)
문자열 s가 주어졌을 때, Palindrom이 되는 3글자로 된 부분 문자열의 종류 찾는 것입니다.
(중복 문자열 제외)

예시 데이터
s = "asafa"
answer = 3
asa (asafa의 부분 문자열)
asa (asafa의 부분 문자열)
afa (asafa의 부분 문자열)

풀이

문자열의 크기는 최대 $10^5$까지 들어오기 때문에 $O(N^3)$의 풀이로는 해결하지 못한다.
(단순히 반복문 3개를 이용하여 first, middle, last를 찍으며 푸는 방식)

풀이1 (내 풀이)

각 알파벳마다 처음(first)과 끝(last)에 등장하는 인덱스를 기록하고,
$first < i < last$를 만족하는 $s[i] \notin temp\_set$을 구하면 된다.

조금 쉽게 표현하면,
3글자로 된 팰린드롬은 1번째 글자와 3번째 글자는 같아야 하며,
그 가운데에 들어가는 알파벳의 종류만 구하면 된다는 뜻이다.

struct Postion {
    int first;
    int last;
};

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<Postion> letters_position(26, {-1, -1});
        for (int i = 0; i < s.size(); i++) {
            char cur = s[i] - 'a';
            if (letters_position[cur].first == -1)
                letters_position[cur].first = i;
            letters_position[cur].last = i;
        }

        int answer = 0;
        for (auto position : letters_position) {
            int left = position.first;
            int right = position.last;
            if (left == -1)
                continue;

			// 가운데에 들어가는 알파벳 중에 유니크한 것들만 뽑아내기 위해 set을 사용
            unordered_set<char> temp_set;
            for (int i = left + 1; i < right; i++) {
                temp_set.insert(s[i]);
            }
            answer += temp_set.size();
        }

        return answer;
    }
};

풀이2 (시간 복잡도 개선)

내 방식의 풀이는 $O(N + 26N)$ 이지만,
지금 서술할 풀이는 $O(N + 27^2 * log(N))$으로 조금 더 최적화 된 풀이이다.
(상수값이 최적화 됨, 단 push_back으로 인한 연산은 배제)

먼저 각 알파벳의 등장 인덱스를 오름차순으로 저장한다.

그리고 팰린드롬의 가운데에 들어갈 알파벳(두 번째 글자)이
첫 번째 글자와 세 번째 글자의 인덱스 사이에 존재하는지를upper_bound를 이용해 검사하는 방식이다.
(upper_bound의 사용으로 상수값이 최적화됨)

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<vector<int>> pos(26);
        for (int i = 0; i < s.size(); i++) {
            pos[s[i] - 'a'].push_back(i);
        }
        
        int ans = 0;
        
        // 문자 X 선택
        for (int x = 0; x < 26; x++) {
            auto &vx = pos[x];
            // 팰린드롬이 만들어질 수 없는 케이스
            if (vx.size() < 2) continue;   
            
            int left = vx.front();
            int right = vx.back();
            
            // 중간에 들어갈 문자 Y 검사
            for (int y = 0; y < 26; y++) {
                auto &vy = pos[y];
                
                // index1 보다 큰 첫 위치 찾기
                auto it = upper_bound(vy.begin(), vy.end(), left);
                
                // 중간 영역에 있는지 확인
                if (it != vy.end() && *it < right)
                    ans++;
            }
        }
        
        return ans;
    }
};