算法题 重构字符串

重构字符串

问题描述

给定一个字符串s，检查是否能重新排列其中的字符，使得任意两个相邻的字符都不相同。

如果可以重新排列，返回任意一个满足条件的字符串。如果不能，返回空字符串""。

示例：

输入: s = "aab" 输出: "aba" 输入: s = "aaab" 输出: ""

算法思路

核心思想是优先处理出现频率最高的字符。

关键：

1. 可行性：如果某个字符的出现次数超过(n + 1) / 2（n为字符串长度），则无法重构
   • 例如：长度为4，最多允许2个相同字符；长度为5，最多允许3个相同字符
2. 贪心策略：总是优先放置当前剩余最多的字符，要避免与前一个字符相同

方法：

• 优先队列（最大堆）：按字符频率排序，每次取出频率最高的字符
• 间隔放置：先将最高频字符放在偶数位置，再填充其他字符

代码实现

方法一：优先队列

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)]
• 步骤：
  1. 取a，结果=“a”，堆：[(b,1)]，prev=(a,1)
  2. 取b，结果=“ab”，堆：[(a,1)]，prev=(b,0)
  3. 取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")+"\"");// ""}

关键点

1. 可行性：

   • 关键条件：maxFreq <= (n + 1) / 2

2. 贪心策略：

   • 优先处理高频字符，避免最后无法放置
   • 间隔放置确保相同字符不相邻

3. 索引：

   • 先使用偶数索引（0,2,4…）
   • 偶数索引用完后使用奇数索引（1,3,5…）
   • 保证了最优的字符分布

4. 字符表示：

   • 使用数组索引0-25表示’a’-‘z’
   • 节省空间且访问高效

5. 边界情况：

   • 空字符串、单字符、两字符等特殊情况
   • 最大频次等于边界值的情况

常见问题

1. 为什么可行性条件是(n+1)/2？

   • 对于偶数长度n，最多能放置n/2个相同字符
   • 对于奇数长度n，最多能放置(n+1)/2个相同字符
   • 统一写成(n+1)/2可以处理两种情况

2. 为什么间隔放置策略有效？

   • 最高频字符占据最优位置（间隔最大）
   • 其他字符频率更低，更容易找到合适位置
   • 偶数位置用完后，奇数位置必然足够

3. 优先队列为什么需要prev变量？

   • 防止连续使用同一个字符
   • 将刚使用的字符暂时移除，下一轮再放回