算法题 重构字符串
重构字符串
问题描述
给定一个字符串s，检查是否能重新排列其中的字符，使得任意两个相邻的字符都不相同。
如果可以重新排列，返回任意一个满足条件的字符串。如果不能，返回空字符串""。
示例：
输入: s = "aab" 输出: "aba" 输入: s = "aaab" 输出: ""算法思路
核心思想是优先处理出现频率最高的字符。
关键：
- 可行性：如果某个字符的出现次数超过
(n + 1) / 2（n为字符串长度），则无法重构- 例如：长度为4，最多允许2个相同字符；长度为5，最多允许3个相同字符
- 贪心策略：总是优先放置当前剩余最多的字符，要避免与前一个字符相同
方法：
- 优先队列（最大堆）：按字符频率排序，每次取出频率最高的字符
- 间隔放置：先将最高频字符放在偶数位置，再填充其他字符
代码实现
方法一：优先队列
importjava.util.*;classSolution{/** * 使用优先队列重构字符串，确保相邻字符不同 * * @param s 输入字符串 * @return 重构后的字符串，如果无法重构返回空字符串 */publicStringreorganizeString(Strings){// 1: 统计每个字符的频率int[]charCount=newint[26];for(charc:s.toCharArray()){charCount[c-'a']++;}// 2: 检查可行性 - 任何字符频率不能超过 (n+1)/2intn=s.length();for(intcount:charCount){if(count>(n+1)/2){return"";}}// 3: 构建最大堆，按频率排序// 堆中存储 [字符, 频率]PriorityQueue<int[]>maxHeap=newPriorityQueue<>((a,b)->b[1]-a[1]);for(inti=0;i<26;i++){if(charCount[i]>0){maxHeap.offer(newint[]{i,charCount[i]});}}// 4: 重构字符串StringBuilderresult=newStringBuilder();int[]prev=null;// 记录上一次使用的字符，避免连续使用while(!maxHeap.isEmpty()){// 取出频率最高的字符int[]current=maxHeap.poll();// 将字符添加到结果中result.append((char)('a'+current[0]));current[1]--;// 频率减1// 如果上一个字符还有剩余，重新放回堆中if(prev!=null&&prev[1]>0){maxHeap.offer(prev);}// 更新prev为当前字符prev=current;}// 如果结果长度等于原字符串长度，说明重构成功returnresult.length()==n?result.toString():"";}}方法二：间隔放置
classSolution{/** * 使用间隔放置策略重构字符串 * * @param s 输入字符串 * @return 重构后的字符串，如果无法重构返回空字符串 */publicStringreorganizeString(Strings){// 1: 统计字符频率int[]charCount=newint[26];intmaxFreq=0;charmaxChar=' ';for(charc:s.toCharArray()){charCount[c-'a']++;if(charCount[c-'a']>maxFreq){maxFreq=charCount[c-'a'];maxChar=c;}}// 2: 检查可行性intn=s.length();if(maxFreq>(n+1)/2){return"";}// 3: 创建结果字符数组char[]result=newchar[n];// 4: 先将最高频字符放在偶数位置 (0, 2, 4, ...)intindex=0;while(charCount[maxChar-'a']>0){result[index]=maxChar;index+=2;charCount[maxChar-'a']--;}// 5: 填充其他字符for(inti=0;i<26;i++){while(charCount[i]>0){// 如果偶数位置已满，切换到奇数位置if(index>=n){index=1;}result[index]=(char)('a'+i);index+=2;charCount[i]--;}}returnnewString(result);}}算法分析
时间复杂度：
- 方法一：O(n log k)，k是不同字符的数量（最多26），实际为O(n)
- 方法二：O(n) - 只需要遍历字符串常数次
空间复杂度：
- 所有方法：O(1) - 字符计数数组大小固定为26
- 结果字符串空间不计入空间复杂度
算法过程
1：s = “aab”
方法一（优先队列）：
- 字符频率：a=2, b=1
- 堆：[(a,2), (b,1)]
- 步骤：
- 取a，结果=“a”，堆：[(b,1)]，prev=(a,1)
- 取b，结果=“ab”，堆：[(a,1)]，prev=(b,0)
- 取a，结果=“aba”，堆：[]，prev=(a,0)
- 返回"aba"
方法二（间隔放置）：
- 最高频字符：a(频次2)
- 先放a：位置0,2 → [‘a’, ?, ‘a’]
- 放b：位置1 → [‘a’, ‘b’, ‘a’]
- 返回"aba"
2：s = “aaab”
- 字符频率：a=3, b=1
- 长度=4，最大允许频次=(4+1)/2=2
- a的频次3 > 2，返回""
3：s = “vvvlo”
- 字符频率：v=3, l=1, o=1
- 长度=5，最大允许频次=3
- v的频次=3 <= 3，可以重构
- 间隔放置：v在位置0,2,4 → [‘v’,?, ‘v’,?, ‘v’]
- 填充l,o：位置1,3 → [‘v’,‘l’,‘v’,‘o’,‘v’]
- 返回"vlvov"
测试用例
publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1: \""+solution.reorganizeString("aab")+"\"");// "aba"// 测试用例2：无法重构System.out.println("Test 2: \""+solution.reorganizeString("aaab")+"\"");// ""// 测试用例3：单字符System.out.println("Test 3: \""+solution.reorganizeString("a")+"\"");// "a"// 测试用例4：两个不同字符System.out.println("Test 4: \""+solution.reorganizeString("ab")+"\"");// "ab" or "ba"// 测试用例5：复杂情况System.out.println("Test 5: \""+solution.reorganizeString("vvvlo")+"\"");// "vlvov"// 测试用例6：边界情况 - 最大频次刚好等于(n+1)/2System.out.println("Test 6: \""+solution.reorganizeString("aaaabc")+"\"");// 长度6，max=4，(6+1)/2=3，4>3 → ""// 测试用例7：长度为奇数的最大频次System.out.println("Test 7: \""+solution.reorganizeString("aaabc")+"\"");// 长度5，max=3，(5+1)/2=3 → 可以重构// 测试用例8：所有字符都不同System.out.println("Test 8: \""+solution.reorganizeString("abcdef")+"\"");// 原字符串即可// 测试用例9：空字符串System.out.println("Test 9: \""+solution.reorganizeString("")+"\"");// ""// 测试用例10：两个相同字符System.out.println("Test 10: \""+solution.reorganizeString("aa")+"\"");// ""}关键点
可行性：
- 关键条件：
maxFreq <= (n + 1) / 2
- 关键条件：
贪心策略：
- 优先处理高频字符，避免最后无法放置
- 间隔放置确保相同字符不相邻
索引：
- 先使用偶数索引（0,2,4…）
- 偶数索引用完后使用奇数索引（1,3,5…）
- 保证了最优的字符分布
字符表示：
- 使用数组索引0-25表示’a’-‘z’
- 节省空间且访问高效
边界情况：
- 空字符串、单字符、两字符等特殊情况
- 最大频次等于边界值的情况
常见问题
为什么可行性条件是
(n+1)/2？- 对于偶数长度n，最多能放置n/2个相同字符
- 对于奇数长度n，最多能放置(n+1)/2个相同字符
- 统一写成
(n+1)/2可以处理两种情况
为什么间隔放置策略有效？
- 最高频字符占据最优位置（间隔最大）
- 其他字符频率更低，更容易找到合适位置
- 偶数位置用完后，奇数位置必然足够
优先队列为什么需要prev变量？
- 防止连续使用同一个字符
- 将刚使用的字符暂时移除，下一轮再放回