0767. 重构字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

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

返回 s 的任意可能的重新排列。若不可行，返回空字符串 ""。

示例 1：

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

示例 2：

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

---

提示：

• 1 <= s.length <= 500
• s 只包含小写字母

2. 🎯 s.1 - 贪心

c

char* reorganizeString(char* s) {
    int freq[26] = {0};
    int n = strlen(s);
    for (int i = 0; i < n; i++) freq[s[i] - 'a']++;
    int maxFreq = 0, maxChar = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > maxFreq) { maxFreq = freq[i]; maxChar = i; }
    }
    if (maxFreq > (n + 1) / 2) return "";
    char* res = (char*)malloc(n + 1);
    res[n] = '\0';
    int idx = 0;
    while (freq[maxChar] > 0) {
        res[idx] = maxChar + 'a';
        freq[maxChar]--;
        idx += 2;
    }
    for (int i = 0; i < 26; i++) {
        while (freq[i] > 0) {
            if (idx >= n) idx = 1;
            res[idx] = i + 'a';
            freq[i]--;
            idx += 2;
        }
    }
    return res;
}

js

/**
 * @param {string} s
 * @return {string}
 */
var reorganizeString = function (s) {
  const freq = new Array(26).fill(0)
  for (const c of s) freq[c.charCodeAt(0) - 97]++
  const n = s.length
  let maxFreq = 0,
    maxChar = 0
  for (let i = 0; i < 26; i++) {
    if (freq[i] > maxFreq) {
      maxFreq = freq[i]
      maxChar = i
    }
  }
  if (maxFreq > Math.floor((n + 1) / 2)) return ''
  const res = new Array(n)
  let idx = 0
  // 先填偶数位
  while (freq[maxChar] > 0) {
    res[idx] = String.fromCharCode(maxChar + 97)
    freq[maxChar]--
    idx += 2
  }
  for (let i = 0; i < 26; i++) {
    while (freq[i] > 0) {
      if (idx >= n) idx = 1
      res[idx] = String.fromCharCode(i + 97)
      freq[i]--
      idx += 2
    }
  }
  return res.join('')
}

py

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - 97] += 1
        n = len(s)
        max_char = max(range(26), key=lambda i: freq[i])
        if freq[max_char] > (n + 1) // 2:
            return ''
        res = [''] * n
        idx = 0
        while freq[max_char] > 0:
            res[idx] = chr(max_char + 97)
            freq[max_char] -= 1
            idx += 2
        for i in range(26):
            while freq[i] > 0:
                if idx >= n:
                    idx = 1
                res[idx] = chr(i + 97)
                freq[i] -= 1
                idx += 2
        return ''.join(res)

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(n)$

算法思路：

• 统计频率，若最大频率 > (n+1)/2 则无解
• 先将频率最高的字母填入偶数位，再依次填入其余字母
• 填完偶数位后继续填奇数位，保证相邻不同