(Python3) - LeetCode (Medium) : 1930. Unique Length-3 Palindromic Subsequences

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

아이디어로 해결해야하는 문자열 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. s에 사용된 고유한 알파뱃들을 저장할 set letters를 선언후 s에 사용된 고유 문자들을 저장합니다.

 

2. 정답변수 ans를 선언 후 0으로 초기화합니다.

📔 풀이과정

다음 palindrome은 모두 'ata'라는 문자열 한개에 대한 부분 문자열입니다.

a__t__a

a_ta___

_a__t_a

palindrome은 어떻게 만들어질까요? 고유한 문자의 왼쪽과 오른쪽 index를 찾고 그 사이 아무문자를 사용해 길이 총 3개의 문자열을 만든다면 palindrome이 됩니다. 

palindrome을 찾기 위해서는 다음 과정을 수행합니다.

1. letters의 문자에 대해 for loop를 수행합니다.

  1-1. 현재 문자의 왼쪽에서 첫번째로 나온 index와 오른쪽에서 첫번째로 나온 index를 첮어 각각 i,j에 저장합니다.

 

  1-2. 만들어진 palindrome을 저장할 set between을 선언해줍니다. 겹치는 것을 방지하기 위함입니다.

 

  1-3. i+1  ~ j-1까지 for loop를 수행하며 선택된 문자를 between에 저장합니다.

 

  1-4. between의 길이를 ans에 누적해 더해줍니다.

 

 

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 Python3

from collections import defaultdict
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        letters = set(s)
        ans = 0
        for ch in letters:
            i, j = s.index(ch), s.rindex(ch)
            between = set()
            for k in range(i+1, j):
                between.add(s[k])
            ans += len(between)
        return ans

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.