[LeetCode] 1930. Unique Length-3 Palindromic Subsequences (Python)

 

난이도: 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".

 

문제 예제 

---

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

 

제한 사항

---

• 3 <= s.length <= 10^5
• s consists of only lowercase English letters.

 

✏️ Solution(솔루션)

---

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        n = len(s)
        answer = 0
        check = defaultdict(bool)

        for i in range(n):
            j = n - 1
            left = s[i]
            if not check[left]:
                while s[j] != left:
                    j-=1
                answer += len(set(s[i+1:j]))
            check[left] = True

        return answer

 

3글자의 팰린드롬을 찾으면 되기 때문에, 사실상 첫번째 알파벳과 세번째 알파벳이 같으면 그 사이에는 어떤 문자가 와도 팰린드롬을 만족한다.

 

따라서, s의 첫번째 알파벳부터 시작하여 이를 left로 설정하고, s의 끝 index를 j로 설정해 left와 같아지는 s[j]가 될 때까지 j를 1씩 빼주었다.

 

그러다가 left와 s[j]가 같은 알파벳이 되었다고 한다면, i와 j 사이에있는 알파벳 수를 중복을 제거하고 answer에 이를 더해주었다 (answer += len(set(s[i+1:j]))).

 

또한 defaultdict을 이용하여 이미 처리한 알파벳을 관리하여 중복 처리를 방지 하였다.

 

마지막으로 answer를 return하여 정답을 맞출 수 있었다.

---

문제: 1930. Unique Length-3 Palindromic Subsequences

깃허브: github

algorithm_practice/LeetCode/2059-unique-length-3-palindromic-subsequences at main · laewonJeong/algorithm_practice