```python
class Solution:
    MAX_K = 1_000_001

    def smallestPalindrome(self, s: str, k: int) -> str:
        n = len(s)
        half = s[:n // 2]
        mid = s[n // 2] if n % 2 == 1 else ""

        cnt = [0] * 26
        for c in half:
            cnt[ord(c) - ord('a')] += 1

        # 总排列数不足 k
        if self.count_arrangements(cnt) < k:
            return ""

        half_len = len(half)
        ans = []

        for _ in range(half_len):
            for i in range(26):
                if cnt[i] == 0:
                    continue
                # 尝试将字符 i 填入当前位
                cnt[i] -= 1
                ways = self.count_arrangements(cnt)
                if k <= ways:
                    ans.append(chr(ord('a') + i))
                    break
                else:
                    # 该分支不包含目标，恢复并跳过
                    cnt[i] += 1
                    k -= ways

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

    def count_arrangements(self, cnt: list[int]) -> int:
        """计算多重集排列数，超过 MAX_K 时截断"""
        total = sum(cnt)
        res = 1
        for c in cnt:
            if c == 0:
                continue
            res *= self.comb(total, c)
            if res >= self.MAX_K:
                return self.MAX_K
            total -= c
        return res

    def comb(self, n: int, k: int) -> int:
        """组合数 C(n, k)，超过 MAX_K 时截断"""
        k = min(k, n - k)
        res = 1
        for i in range(1, k + 1):
            res = res * (n - i + 1) // i
            if res >= self.MAX_K:
                return self.MAX_K
        return res
```

核心思路

回文串由左半部分唯一确定（奇数长度时中间字符固定），因此问题转化为求左半部分字符串的第 k 小不同排列。

1. 多重集排列数：用组合数连乘 `C(n, v1) * C(n-v1, v2) * ...` 计算，避免阶乘溢出。由于 `k ≤ 10^6`，乘积超过 `1_000_001` 时直接截断。
2. 贪心构造：从左到右逐位确定，从小到大枚举 `'a'~'z'`，尝试将当前字符填入该位，计算剩余位置的排列数 `ways`。若 `k ≤ ways`，则确定该位；否则 `k -= ways` 并尝试下一个字符。
3. 复杂度：时间 `O(|half| * 26 * log(k))`，空间 `O(1)`。