LeetCode 767. 重构字符串

约 6 分钟
文章信息 9 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 华为 微软 拼多多
标签
字符串 哈希表 排序 贪心 堆（优先队列） 计数

题目描述

✅ 767. 重构字符串

image-20260928223210716

题意分析

重排只含小写字母的字符串，使任意相邻字符不同，并保留每种字符的原有次数。返回任意合法排列；无法做到时返回空串。

解法：最高频字符优先填偶数位

核心思路

[!blue]

设字符串长度为 n，最高频次为 m。要隔开这 m 个相同字符，至少需要 m - 1 个其他字符，因此必须满足 n - m >= m - 1，即 m <= ceil(n / 2)。令 E = ceil(n / 2)，它也正好是下标从零开始时偶数位置的数量；若 m > E，直接判定无解。

满足上限时，先把最高频字符放到下标 0, 2, 4, ...。再按字母顺序取其他字符，继续填剩余偶数位；偶数位用完后，从下标 1 开始填奇数位。每种字符一次填完，无需将剩余字符按频次排序。

只落在偶数位或只落在奇数位的同一种字符，位置相隔二，显然不会相邻。还需要证明：某种字符先填偶数位末尾，再填奇数位开头时，两部分也不会相邻。

设这个跨段字符出现 k 次，开始填写前已有 s 个偶数位被占用，所以它的第一个偶数下标是 2s。最高频字符已经填完，且当前仍有偶数位可填，因此 k <= m <= s < E。它先用掉剩余的 E - s 个偶数位，再占用 b = k - E + s 个奇数位。由于 k < E，得到 b < s：最后一个奇数下标 2b - 1 至多为 2s - 3，与第一个偶数下标 2s 至少相差三。两部分也不会相邻。

每次写入都减少一次计数，所有字符共写入 n 次，恰好填满全部偶数位和奇数位。这样既保留了每种字符的数量，也构造出了合法结果，说明最高频次上限同时是必要和充分条件。

解题步骤

  1. 用 count 统计 26 个字母的次数，用 maxIndex 记录最高频字符。
  2. 若最高频次大于 (n + 1) / 2，返回空字符串。
  3. 建立长度为 n 的结果数组，令 position = 0，先每隔一位写入最高频字符，并将其计数减至零。
  4. 按字母遍历剩余计数。每次写入前，若 position >= n，将它切换到 1；写入后让位置增加二、计数减一。
  5. 所有计数归零后，将结果数组转换成字符串。

代码实现

class Solution {
    public String reorganizeString(String s) {
        int[] count = new int[26];
        int maxIndex = 0;

        for (char c : s.toCharArray()) {
            int index = c - 'a';

            count[index]++;

            if (count[index] > count[maxIndex]) {
                maxIndex = index;
            }
        }

        // 最高频字符需要足够其他字符隔开，超出偶数位数量便无解。
        if (count[maxIndex] > (s.length() + 1) / 2) {
            return "";
        }

        char[] ans = new char[s.length()];
        int position = 0;

        while (count[maxIndex] > 0) {
            ans[position] = (char) ('a' + maxIndex);
            position += 2;
            count[maxIndex]--;
        }

        for (int index = 0; index < count.length; index++) {
            while (count[index] > 0) {
                if (position >= ans.length) {
                    // 偶数位置用完后转到奇数位置，不能重新覆盖下标零。
                    position = 1;
                }

                ans[position] = (char) ('a' + index);
                position += 2;
                count[index]--;
            }
        }

        return new String(ans);
    }
}

func reorganizeString(s string) string {
    count := [26]int{}
    maxIndex := 0
    for i := range s {
        index := int(s[i] - 'a')
        count[index]++
        if count[index] > count[maxIndex] {
            maxIndex = index
        }
    }
    // 最高频字符需要足够其他字符隔开，超出偶数位数量便无解。
    if count[maxIndex] > (len(s)+1)/2 {
        return ""
    }

    ans := make([]byte, len(s))
    position := 0
    for count[maxIndex] > 0 {
        ans[position] = byte('a' + maxIndex)
        position += 2
        count[maxIndex]--
    }

    for index := range count {
        for count[index] > 0 {
            if position >= len(ans) {
                // 偶数位置用完后转到奇数位置，不能重新覆盖下标零。
                position = 1
            }
            ans[position] = byte('a' + index)
            position += 2
            count[index]--
        }
    }
    return string(ans)
}

复杂度分析

  • 时间复杂度：$O(n + C)$，其中字符集大小 C = 26。统计扫描 n 个字符，构造也只写入 n 次，外层额外遍历字符集。
  • 空间复杂度：$O(n + C)$。结果数组占 $O(n)$，计数数组占 $O(C)$；即使不计返回字符串，构造数组仍需要线性空间。

关键点总结

[!green]

  • 最高频字符所需的间隔数给出可行条件：maxCount <= ceil(n / 2)。
  • 先放最高频字符，使其他字符跨越偶、奇两段时仍能保持间隔；余下字符不必排序。
  • 每个字符的全部出现连续处理，计数减至零后就不再写入，保证既不遗漏也不增加字符。

易错点总结

[!yellow]

  • 上限用 n / 2 会在奇数长度下少算一个位置；最高频次等于上限仍然可行，不能用 >= 判无解。
  • 偶数位用完后应切换到下标 1，不能回到 0 覆盖已写字符。
  • 只说“每次下标加二”不足以保证正确，切换奇偶位置时还依赖最高频字符已经优先填完。
  • 每次写入都要递减计数；全部 n 个位置写满时计数也已全部归零，不会再从奇数位末尾绕回。

相似题目

题目 难度 关联与区别
358. K 距离间隔重排字符串 困难 原题要求相同字符相距至少k，本题只禁止相邻相同，可对比频次上限与可行构造。
621. 任务调度器 中等 同样避免相同类型靠得太近，原题允许加入空闲，本题必须只重排原字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/93774079
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！