[LeetCode] 1930. Unique Length-3 Palindromic Subsequences

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/

Unique Length-3 Palindromic Subsequences - LeetCode

leetcode - Unique Length-3 Palindromic Subsequences

문제 유형 : 문자열 처리 / 집합 / 투 포인터

문제 난이도 : Medium

 

문제

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

문자열 s가 주어진다. 이 안에서 길이가 3인 팰린드롬의 부분열을 구하시오.

중복은 있어도 하나로 간주됩니다.

팰린드롬은 뒤집어도 같은 걸 말합니다.

부분열은 기존 문자열에서 순서를 그대로 사용한 새로 만들어진 문자열이어야 합니다.

 

예를 들어 "ace"는 "abcde"에서 만들 수 있습니다.

 

 

풀이

길이가 3인 팰린드롬은 (문자)*(문자)의 형태를 가진다.

여기서 중복을 안센다면, 각 문자별로 가장 양 끝의 범위의 사이에 있는 문자들의 집합의 크기를 누적시키면 구할 수 있다.

 

즉, 양쪽 끝의 알파벳은 같고 가운데에 뭐가 올수있느냐가 중요하다.

각 알파벳 영소문자별로 처음 위치와 마지막 위치를 구해놓는다.

각 알파벳에 대해, 사이에 어떤 알파벳들이 있는지들을 모두 누적하면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size();
        vector<pair<int, int>> apperance(26, {-1, -1}); // {first, last};
        for(int i = 0; i < n; ++i) {
            if(apperance[s[i] - 'a'].first == -1)
                apperance[s[i] - 'a'].first = i;
            apperance[s[i] - 'a'].second = i;
        }

        int ans = 0;
        for(int ch = 0; ch < 26; ++ch) {
            int start = apperance[ch].first;
            int end = apperance[ch].second;
            if(end - start < 2) continue;
            unordered_set<char> chars;
            for(int i = start+1; i < end; ++i) {
                chars.insert(s[i]);
            }
            ans += chars.size();
        }

        return ans;
    }
};