A.每日一题：3517. 最小回文排列 I

题目链接：3517. 最小回文排列 I（中等）

算法原理：

解法一：计数排序

时间复杂度O(N)

写法一：StringBuffer

79ms击败5.76%

1.思路很简单，利用计数排序的思想，既然字符串给的是回文的，那么我们只需要统计前一半就行了，统计前一半中26个小写英文字符出现的次数，然后从 a 遍历到 z 依次拼接即可

2.拼接之后，后半部分就直接翻转过来再接上，这一点用 StringBuffer 可以很简单的实现

3.最后一点就是看这个回文串长度是奇数还是偶数，我们上述做法得到的回文串必定是偶数的，如果是奇数的话差的一定是中间的那个，而中间的那个在最终结果的位置必然还是在中间，否则这个字符串必然不再是回文，因此我们直接把原字符串的正中间的字符取出来接在中间即可

4.最后根据原字符串的奇偶长度返回不同的结果即可

写法二：StringBuilder

33ms击败54.86%

思路与写法一完全相同，但这个会更快，因为 StringBuffer 是线程安全的，中间加了很多锁，而 StringBuffer 是线程不安全的，没有那么多锁，效率要比 StringBuffer 快不少

关于线程中上锁的知识可参考👇

Java EE：2.多线程-初阶（第四弹）：synchronized 锁+内存可见性

Java EE：3.多线程-进阶（第一弹）：常见的锁策略+synchronized原理

优化

16ms击败98.96%

中间重复添加相同字符的部分可以借助 repeat 实现

String a = "a"; String fiveAs = a.repeat(5); // 结果就是 "aaaaa"

解法二：排序左半部分

48ms击败15.03%

时间复杂度O(n logn)

由于 s 是回文字符串，我们只需关心左半部分如何排列即可，因此我们可以将左半部分拿出来排列后在用 StringBuilder 拼接上去，后半部分只需要逆序拼接即可

Java代码：

class Solution { //3517. 最小回文排列 I //解法一：计数排序-写法一：StringBuffer public String smallestPalindrome(String s) { if(s.length()==1) return s; int[] hash=new int[26]; StringBuffer cur=new StringBuffer(); for(int i=0;i<s.length()/2;i++) hash[s.charAt(i)-'a']++; for(int i=0;i<26;i++) while(hash[i]-->0) cur.append((char)(i+'a')); if(s.length()%2==0) return cur.toString()+cur.reverse().toString(); else return cur.toString()+s.charAt(s.length()/2)+cur.reverse().toString(); } }

class Solution { //3517. 最小回文排列 I //解法一：计数排序-写法二：StringBuilder public String smallestPalindrome(String s) { if(s.length()==1) return s; int[] hash=new int[26]; StringBuilder cur=new StringBuilder(); for(int i=0;i<s.length()/2;i++) hash[s.charAt(i)-'a']++; for(int i=0;i<26;i++) while(hash[i]-->0) cur.append((char)(i+'a')); if(s.length()%2==0) return cur.toString()+cur.reverse().toString(); else return cur.toString()+s.charAt(s.length()/2)+cur.reverse().toString(); } }

class Solution { //3517. 最小回文排列 I //解法一：计数排序-优化 public String smallestPalindrome(String s) { int n=s.length(); if(n==1) return s; int[] hash=new int[26]; StringBuilder cur=new StringBuilder(); for(int i=0;i<n/2;i++) hash[s.charAt(i)-'a']++; for(int i=0;i<26;i++) cur.repeat('a'+i,hash[i]); //提前拷贝一份 StringBuilder t=new StringBuilder(cur); //回文串长度为奇数就把中间的加上 if(n%2==1) cur.append(s.charAt(n/2)); cur.append(t.reverse()); return cur.toString(); } }

class Solution { //3517. 最小回文排列 I //解法二：排序左半部分 public String smallestPalindrome(String s) { int n=s.length(); int m=n/2; char[] t=s.substring(0,m).toCharArray(); Arrays.sort(t); StringBuilder cur=new StringBuilder(); cur.append(t); //判断是否是奇数长度回文串 if(n%2==1) cur.append(s.charAt(m)); //逆序拼接 for(int i=m-1;i>=0;i--) cur.append(t[i]); return cur.toString(); } }