重构字符串

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，767. Reorganize String

先看题目描述

DREtW6.png

大意就是给定一个字符串 S，让我们判断能否重构该字符串，使字符串的相邻字母均不相同，能的话就返回重构后字符串，不能的话则返回空串

算法和思路

ps：这题不会做，想到了用计数排序，但用计数排序写了一半后，不知道该怎么利用频次数组来重构字符串，于是就去看题解了..

设字符串长度为 n，我们需要先遍历字符串并用一个频次数组 cnt 统计每个字母的出现次数，同时用一个变量 max 维护所有字母中的最大出现次数。统计结束后，若 max > (n + 1) / 2，则无法重新排布字母使得相邻的字母都不相同，返回空串；若 max <= (n + 1) / 2，则考虑如何重新排布字母

基于计数的贪心算法

首先统计每个字母的出现次数，然后根据每个字母的出现次数重构字符串

当 n 是奇数且出现最多的字母的出现次数是 (n+1)/2 时，出现次数最多的字母必须全部放置在偶数下标，否则一定会出现相邻的字母相同的情况。其余情况下，每个字母放置在偶数下标或者奇数下标都是可行的

维护偶数下标 evenIndex 和奇数下标 oddIndex，初始值分别为 0 和 1。遍历每个字母，根据每个字母的出现次数判断字母应该放置在偶数下标还是奇数下标

首先考虑是否可以放置在奇数下标。根据上述分析可知，只要字母的出现次数不超过字符串的长度的一半（即出现次数小于或等于 n/2），就可以放置在奇数下标，只有当字母的出现次数超过字符串的长度的一半时，才必须放置在偶数下标。字母的出现次数超过字符串的长度的一半只可能发生在 n 是奇数的情况下，且最多只有一个字母的出现次数会超过字符串的长度的一半

因此通过如下操作在重构的字符串中放置字母

  • 如果字母的出现次数大于 0 且小于或等于 n / 2，且 oddIndex 没有超出数组下标范围，则将字母放置在 oddIndex，然后将 oddIndex 的值加 2
  • 如果字母的出现次数大于 n/2，或 oddIndex 超出数组下标范围，则将字母放置在 evenIndex，然后将 evenIndex 的值加 2

最后返回重构后的字符串即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String reorganizeString(String S) {
        int len = S.length();
        if (len <= 1) return S;
        char[] ss = S.toCharArray();
        char[] res = new char[len];
        int[] cnt = new int[26];
        int max = 0;
        for (char c : ss) {
            cnt[c - 'a']++;
            max = Math.max(max, cnt[c - 'a']);
        }
        if (max > (len + 1) / 2) {
            return "";
        }
        int evenIndex = 0;
        int oddIndex = 1;
        int halfLen = len / 2;
        for (int i = 0; i < 26; i++) {
            char c = (char)('a' + i);
            while (cnt[i] > 0 && cnt[i] <= halfLen && oddIndex < len) {
                res[oddIndex] = c;
                oddIndex += 2;
                cnt[i]--;
            }
            while (cnt[i] > 0) {
                res[evenIndex] = c;
                evenIndex += 2;
                cnt[i]--;
            }
        }
        return new String(res);
    }
}