Permutation

문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-ii 풀이 1번 문제와 마찬가지로 팰린드롬의 성질상 절반만 결정하면 전체가 결정된다. 따라서 이 문제는 절반 문자열의 k번째 사전순 순열을 구하는 문제로 단순화된다. 각 문자의 등장 횟수를 세고, 홀수 번 등장하는 문자는 팰린드롬의 가운데에 배치한다. 나머지는 2로 나눠 halfTable을 만든다. 절반 문자열에는 중복 문자가 있을 수 있으므로, 전체 순열 수는 단순히 $n!$이 아니라 중복 순열 공식으로 구해야 한다. $$\frac{n!}{\prod_{i} n_i!}$$ 여기서 n은 절반 문자열의 길이, n_i는 각 문자의 개수이다. 이 값이 k보다 작으면 k번째 순열이 존재하지 않으므로 빈 문자열을 반환한다. ...