[코테연습] 1930. Unique Length-3 Palindromic Subsequences

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

 

 

문제 타입

• 문자열 처리 문제: 주어진 문자열에서 특정 조건을 만족하는 부분 문자열(길이 3의 팰린드롬)을 찾는 문제.
• 중복 제거 문제: 고유한 조건을 만족하는 조합을 찾아야 하므로, 중복 처리가 핵심.
• 알고리즘 유형: 해시셋(HashSet)을 사용한 고유한 조합 추적 + 배열을 사용한 효율적인 빈도 계산.

---

문제 분석

• 조건:
  1. 길이가 정확히 3인 부분 문자열이어야 함.
  2. 첫 번째 문자와 세 번째 문자가 같아야 팰린드롬 조건을 만족함 (x t x).
• 제약:
  • 문자열의 길이는 최대 10510^5105이므로, 비효율적인 완전 탐색은 사용 불가.
  • 빠른 탐색을 위해 문자열을 한 번 순회하며 해결해야 함.
• 데이터 구조:
  1. 배열: 왼쪽(leftCount)과 오른쪽(rightCount)의 문자의 빈도를 저장.
  2. HashSet: 고유한 길이 3 팰린드롬을 저장.
• 핵심 아이디어:
  • 각 문자를 중간 문자로 설정하고, 왼쪽과 오른쪽에 동일한 문자가 있는지 확인.
  • 팰린드롬을 고유하게 식별하기 위해 "중간 문자 + 양쪽 문자" 조합을 숫자로 변환하여 저장.

---

문제 풀이

• Step 1: 초기화
  • rightCount: 문자열에서 각 문자의 빈도를 저장.
  • leftCount: 문자열을 순회하며 탐색된 문자의 빈도를 저장.
  • uniquePalindromes: 고유한 팰린드롬을 추적하기 위한 HashSet.
• Step 2: 문자열 순회
  1. 각 문자를 중간 문자(middleCharIndex)로 설정.
  2. rightCount에서 현재 문자를 감소시킴(오른쪽에서 제거).
  3. 모든 알파벳(26개)을 순회하며:
     • 왼쪽(leftCount)과 오른쪽(rightCount)에 해당 문자가 모두 존재할 경우:
       • "중간 문자 + 양쪽 문자" 조합을 숫자로 변환하여 uniquePalindromes에 추가.
• Step 3: 왼쪽 빈도 업데이트
  • 현재 문자를 leftCount에 추가(왼쪽에서 탐색된 문자로 업데이트).
• Step 4: 결과 반환
  • uniquePalindromes의 크기를 반환(고유한 팰린드롬 개수).

 

> java

 

class Solution {
    public int countPalindromicSubsequence(String s) {
        // rightCount: 오른쪽에서 남아있는 각 알파벳의 빈도수
        int[] rightCount = new int[26];
        for (char ch : s.toCharArray()) {
            rightCount[ch - 'a']++;
        }

        // leftCount: 왼쪽에서 이미 탐색된 각 알파벳의 빈도수
        int[] leftCount = new int[26];

        // uniquePalindromes: 고유한 길이 3 팰린드롬을 추적하는 HashSet
        HashSet<Integer> uniquePalindromes = new HashSet<>();

        // 문자열 순회
        for (int i = 0; i < s.length(); i++) {
            int middleCharIndex = s.charAt(i) - 'a'; // 현재 문자를 알파벳 인덱스로 변환
            rightCount[middleCharIndex]--; // 현재 문자를 오른쪽 빈도에서 감소

            // 왼쪽과 오른쪽에서 동일한 문자를 찾고 팰린드롬 조합 추가
            for (int charIndex = 0; charIndex < 26; charIndex++) {
                if (leftCount[charIndex] > 0 && rightCount[charIndex] > 0) {
                    // 고유한 팰린드롬을 "중간 문자 + 양쪽 문자" 조합으로 저장
                    uniquePalindromes.add(26 * middleCharIndex + charIndex);
                }
            }

            // 현재 문자를 왼쪽 빈도에 추가
            leftCount[middleCharIndex]++;
        }

        // 고유한 팰린드롬 조합의 개수 반환
        return uniquePalindromes.size();
    }
}

 

 

> python

 

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        right_cnt = [0] * 26
        for ch in s :
           right_cnt[ord(ch) - ord('a')] += 1

        left_cnt = [0] * 26
        result = set()

        for ch in s :
            middle = ord(ch) - ord('a')
            right_cnt[middle]-=1

            for j in range(26) :
                if left_cnt[j] > 0 and right_cnt[j] > 0 :
                    result.add(26 * middle + j)
            left_cnt[middle]+=1

        return len(result)