Leetcode 1930. Unique Length-3 Palindromic Subsequences

문제

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가 주어질때, 해당 문자열의 subsequence로 만들수 있는 길이 3개짜리 회문의 갯수를 구하라
• 다만 중복된 회문은 제외한다.

subsequence : 상대적인 순서는 유지하면서 이어지지 않는 부분 배열
Ex. abcdef > ace 는 해당 문자열의 subsequence

예시

Input: s = "aabca"

-aaa, aba, aca 총 3개의 회문이 있다.

제한

• $3 <= s.length <= 10^5$
• s는 소문자 영단어로만 이루어져 있다.

풀이

1. 각 영문자들이 등장하는 첫번째 index와 끝 index를 찾는다.
2. 그 사이에 위치하는 unique 한 문자의 갯수를 찾는다.

이게 왜 됨?

• 영 문자의 갯수는 총 26개이다.
• 26개의 영문자에 대해 O(N) 으로 순회하니까, 어차피 시간복잡도는 O(N)이 된다.
• 각 영문자에 대해 시작, 끝 점만 저장하니까 공간복잡도는 O(1 * 26), 즉 O(1) 이 된다.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        placement = defaultdict(lambda : [-1, -1])

        for i, ch in enumerate(s):
            if placement[ch][0] == -1:
                placement[ch][0] = i
            else:
                placement[ch][1] = i

        ans = 0

        for val in placement.values():
            if val[0] == -1 or val[1] == -1:
                continue

            mid = s[val[0] + 1: val[-1]]
            ans += len(set(mid))

        return ans