Leetcode 3518. Smallest Palindromic Rearrangement II

문제

You are given a palindromic string s and an integer k. Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string. Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.

회문 문자열 s와 정수 k가 주어집니다.

s의 문자들을 재배열하여 만들 수 있는 회문 중, 사전순으로 k번째로 작은 회문을 반환하세요. 서로 다른 회문 순열의 개수가 k개보다 적다면 빈 문자열을 반환하세요.

참고: 서로 다른 방식으로 재배열했더라도 결과로 만들어진 회문 문자열이 같다면 하나의 경우로만 계산합니다.

예시

입력: s = "abba", k = 2

출력: "baab"

설명:

"abba"의 문자들을 재배열하여 만들 수 있는 서로 다른 회문은 "abba"와 "baab" 두 개입니다.

사전순으로는 "abba"가 "baab"보다 앞섭니다. k = 2이므로 두 번째 회문인 "baab"을 반환합니다.

제한

• $1 <= s.length <= 10^4$
• s는 영어 소문자로만 이루어져 있다.
• s는 반드시 회문이다.
• $1 <= k <= 10^6$

풀이

먼저 전처리를 진행해야 한다.

전처리 1 : 중간에 들어갈 글자 찾기

• s의 각 문자를 카운트한 뒤, 등장 횟수가 홀수인 문자를 찾는다.

전처리 2 : 회문에서 왼쪽에 들어갈 문자만 찾기

• 사전순으로 k번째인 회문은 왼쪽 절반만 k번째로 정렬하면 된다.

  • 왜냐하면 오른쪽의 문자들은 왼쪽의 문자들에 의해 이미 결정되기 때문이다.

• 모든 문자의 등장 횟수를 2로 나눈다.

이론 1

• 길이가 n인 문자열에 (a) 문자가 a개, (b) 문자가 b개 있다면 만들 수 있는 서로 다른 순열의 총개수는 $\frac{n!}{a!b!}$ 이다.

이론 2

• 길이가 n인 문자열에 (a) 문자가 a개, (b) 문자가 b개 있다고 하자.
• 이때 (a) 문자로 시작하는 순열의 개수는 몇 개일까?
• $\frac{n!}{a!b!}$ 에서 분모의 a에 해당하는 값이 하나 줄어들고, 분자의 n에 해당하는 값도 하나 줄어든다.
• 즉, 길이가 n인 순열의 총개수에 (a) 문자의 개수를 곱한 뒤 n으로 나누면, (a) 문자로 시작하는 순열의 개수를 구할 수 있다.

풀이와 연관성

• 먼저 만들 수 있는 순열의 총개수를 구한다.
• 이후 시작할 수 있는 문자를 하나씩 확인하며, 해당 문자로 시작했을 때 만들 수 있는 순열의 개수를 계산한다.
• 만약 k가 해당 개수보다 크다면 그 문자로 시작하는 경우는 건너뛸 수 있으므로, k에서 해당 개수를 뺀 뒤 다음 문자를 확인한다.
• 만약 k가 해당 개수보다 작거나 같다면 반드시 그 문자로 시작해야 하므로, 해당 문자를 왼쪽 문자열에 추가하고 새로운 k와 size를 이용해 탐색을 이어간다.

코드 1 : Iterative

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        N = len(s)

        center = ""
        counter = Counter(s)

        for key, value in counter.items():
            if value % 2:
                center = key
                counter[key] -= 1
            counter[key] //= 2

        counter = [[key, value] for key, value in counter.items() if value != 0]
        counter.sort()

        total = factorial(N // 2)
        for key, value in counter:
            if value == 0:
                continue

            total //= factorial(value)

        ans = []
        size = N // 2

        for i in range(N // 2):
            for index, (key, value) in enumerate(counter):
                if value == 0:
                    continue

                current = total * value // size

                if k <= current:
                    size -= 1
                    counter[index][1] -= 1
                    total = current
                    ans.append(key)
                    break
                else:
                    k -= current
                    continue

            if len(ans) != i + 1:
                return ""

        ans = "".join(ans)
        return ans + center + ans[::-1]

풀이 2 : Recursive

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        N = len(s)
        center = ""
        cntr = Counter(s)

        for key, cnt in cntr.items():
            if cnt % 2:
                center = key
                cntr[key] -= 1
            cntr[key] //= 2

        cntr = [[key, value] for key, value in cntr.items() if value != 0]
        cntr.sort()

        def check(size: int, counter: List[Tuple[str, int]], k_val: int, total: int) -> str:
            if size == 0:
                return ""

            for index, (char, count) in enumerate(counter):
                if count == 0:
                    continue

                current = total * count // size

                if k_val <= current:
                    counter[index][1] -= 1
                    return char + check(size - 1, counter, k_val, current)
                else:
                    k_val -= current

            return ""

        total = factorial(N // 2)

        for char, count in cntr:
            if count != 0:
                total //= factorial(count)

        ans = check(N // 2, cntr, k, total)

        if len(ans) < N // 2:
            return ""

        return ans + center + ans[::-1]