3517. 最小回文排列 I

题目描述

给你一个回文字符串 s。

返回 s 的按字典序排列的最小回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个回文字符串。

排列是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。
如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"

输出： "z"

解释：

仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"

输出： "abbba"

解释：

通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"

输出： "acddca"

解释：

通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成。
保证 s 是回文字符串。

解法

方法一：计数

我们首先统计字符串中每个字符的出现次数，记录在哈希表或数组 \(\textit{cnt}\) 中。由于字符串是回文字符串，因此每个字符的出现次数要么是偶数次，要么有且仅有一个字符出现奇数次。

接下来，我们从字典序最小的字符开始，依次将每个字符的一半次数添加到结果字符串的前半部分 \(\textit{t}\) 中。如果某个字符出现了奇数次，我们将该字符记录为中间字符 \(\textit{ch}\)。最后，我们将 \(\textit{t}\)、\(\textit{ch}\) 和 \(\textit{t}\) 的反转拼接起来，得到最终的按字典序排列的最小回文排列。

Python3JavaC++GoTypeScript

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        cnt = Counter(s)
        t = []
        ch = ""
        for c in ascii_lowercase:
            v = cnt[c] // 2
            t.append(c * v)
            cnt[c] -= v * 2
            if cnt[c] == 1:
                ch = c
        ans = "".join(t)
        ans = ans + ch + ans[::-1]
        return ans

class Solution {
    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

        StringBuilder t = new StringBuilder();
        String ch = "";

        for (char c = 'a'; c <= 'z'; c++) {
            int idx = c - 'a';
            int v = cnt[idx] / 2;
            if (v > 0) {
                t.append(String.valueOf(c).repeat(v));
            }
            cnt[idx] -= v * 2;
            if (cnt[idx] == 1) {
                ch = String.valueOf(c);
            }
        }

        String ans = t.toString();
        ans = ans + ch + new StringBuilder(ans).reverse();
        return ans;
    }
}

class Solution {
public:
    string smallestPalindrome(string s) {
        vector<int> cnt(26);
        for (char c : s) {
            cnt[c - 'a']++;
        }
        string t = "";
        string ch = "";
        for (char c = 'a'; c <= 'z'; ++c) {
            int v = cnt[c - 'a'] / 2;
            if (v > 0) {
                t.append(v, c);
            }
            cnt[c - 'a'] -= v * 2;
            if (cnt[c - 'a'] == 1) {
                ch = string(1, c);
            }
        }
        string ans = t;
        ans += ch;
        string rev = t;
        reverse(rev.begin(), rev.end());
        ans += rev;
        return ans;
    }
};

func smallestPalindrome(s string) string {
    cnt := make([]int, 26)
    for i := 0; i < len(s); i++ {
        cnt[s[i]-'a']++
    }

    t := make([]byte, 0, len(s)/2)
    var ch byte
    for c := byte('a'); c <= 'z'; c++ {
        v := cnt[c-'a'] / 2
        for i := 0; i < v; i++ {
            t = append(t, c)
        }
        cnt[c-'a'] -= v * 2
        if cnt[c-'a'] == 1 {
            ch = c
        }
    }

    totalLen := len(t) * 2
    if ch != 0 {
        totalLen++
    }
    var sb strings.Builder
    sb.Grow(totalLen)

    sb.Write(t)
    if ch != 0 {
        sb.WriteByte(ch)
    }
    for i := len(t) - 1; i >= 0; i-- {
        sb.WriteByte(t[i])
    }
    return sb.String()
}

function smallestPalindrome(s: string): string {
    const ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz';
    const cnt = new Array<number>(26).fill(0);
    for (const chKey of s) {
        cnt[chKey.charCodeAt(0) - 97]++;
    }

    const t: string[] = [];
    let ch = '';
    for (let i = 0; i < 26; i++) {
        const c = ascii_lowercase[i];
        const v = Math.floor(cnt[i] / 2);
        t.push(c.repeat(v));
        cnt[i] -= v * 2;
        if (cnt[i] === 1) {
            ch = c;
        }
    }

    let ans = t.join('');
    ans = ans + ch + ans.split('').reverse().join('');
    return ans;
}

3517. 最小回文排列 I

题目描述

解法

方法一：计数

评论