[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++

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int count = 0;
        vector<int> firstIdx(26, INT_MAX);
        vector<int> lastIdx(26);

        for(int i = 0; i < s.size(); i++) {
            firstIdx[s[i] - 'a'] = min(firstIdx[s[i] - 'a'], i);
            lastIdx[s[i] - 'a'] = i;
        }

        for(int i = 0; i < 26; i++) {
            if(firstIdx[i] < lastIdx[i]) {
                count += set<char>(begin(s) + firstIdx[i] + 1, begin(s) + lastIdx[i]).size();
            }
        }

        return count;
    }
};