1930. Unique Length-3 Palindromic Subsequences

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:12:21

 

---

 

문제 설명

 

 

문자열 s가 주어졌을 때, s의 부분 문자열 중 길이 3의 유일한 펠린드롬의 개수를 반환하라.

같은 부분 문자열을 만드는 여러 방법이 있다고 해도, 이는 1개로 세어짐에 유의하라.

 

펠린드롬은 앞으로, 뒤로 읽어도 같은 문자열을 의미한다.

부분 문자열은 원본 문자열에서 일부 문자(안 쓸 수도 있다)를, 남은 문자들의 상대적인 순서를 바꾸지 않고 제거함으로써 얻어지는 새로운 문자열이다.

 

---

 

풀이

 

해시를 사용하자. (거듭 말하지만, 파이썬에서 해시 - set, dict을 바로 떠올리면 되서 편하다)

 

우선 우리는 알파벳 a ~ z까지, 그 알파벳이 처음 등장하는 인덱스와 마지막에 등장하는 인덱스를 조사할 수 있다. (우리는 길이 3의 팰린드롬을 만드므로 처음과 끝 문자열만이 같으면 된다, 또한 유일성을 구하려면 가장 범위가 넓은 처음 ~ 끝 인덱스를 딱 한번만 조사하는 게 편리할 것이다.

 

이렇게 구한 알파벳 인덱스를 이용하자. 여기서 해시를 쓰면 되는데, (첫 인덱스 ~ 끝 인덱스) 사이의 문자들의 유일한 집합을 구하기만 하면 되기 때문이다.

 

a

b

d

a

a

d

b

c

a

 

위의 예시를 보자. 두 a 사이에 문자열들이 존재하고, 이 중 유일한 문자 집합은 (b, d, a, c)가 된다. 길이 3의 팰린드롬을 구하려면 첫 문자 + (유일한 문자 집합 원소) + 끝 문자 조합을 만들면 된다. 경우의 수는 유일한 문자 집합의 길이와 동일하다.

 

정리하면...

 

• 각 알파벳에 대해 처음과 마지막으로 등장하는 인덱스를 조사하고
• 그 알파벳마다 순회하며 유일한 문자 집합의 길이를 구하여
• 모든 길이를 합하면 된다.

 

 

풀이 코드

class Solution:
    def countUniqueCharacter(self, s: str, start: int, end: int) -> int:
        result = set()
        for i in range(start+1, end):
            result.add(s[i])
        return len(result)

    def countPalindromicSubsequence(self, s: str) -> int:
        position_dict = dict()

        for i in range(len(s)):
            if s[i] not in position_dict:
                position_dict[s[i]] = [i, i]
            else :
                position_dict[s[i]][1] = i

        result = 0
        for left, right in position_dict.values() :
            result += self.countUniqueCharacter(s, left, right)
        return result