重构字符串

2020-11-30

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

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorganize-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

先把字符串进行桶计数
每次先选数量最多的，当前字符的计数减1
再选数量次多的一个字符（不和前一个相同），当前字符的计数减一
如果某一次选不到任何一个字符并且还没结束，那么就不能满足，直接返回空

class Solution {
    public String reorganizeString(String S) {
        int[] bucket = new int[26];
        for (int i = 0; i < S.length(); i++) {//桶计数每个字符的数量
            bucket[S.charAt(i) - 'a']++;
        }
        StringBuilder bd = new StringBuilder();

        int len = S.length();
        while (len > 0) {
            int index = getMaxIndex(bucket, -1);//因为前一个字符串一定和当前字符串不同，并且数量肯定会同减，所以两个中的第一个不需要限制
            bucket[index]--;
            len--;
            bd.append((char) (index + 'a'));
            index = getMaxIndex(bucket, index);//两个中的第二个一定不能和前一个相同
            if (index > -1) {//如果有符合条件的index了，那么加入到字符串中
                bd.append((char) (index + 'a'));
                bucket[index]--;
                len--;
            } else {//如果没有符合条件的index了，那么结束
                break;
            }

        }
        for (int i = 0; i < 26; i++) {
            if (bucket[i] > 0) {//如果某个元素还没有被用完，不能符合题意
                return "";
            }
        }

        return bd.toString();
    }
    public static int getMaxIndex(int[] bucket, int lastIndex) {//统计当前桶中数量最多的字符的下标，lastIndex是上次选择的字符的下标
        int max = 0;
        int index = -1;
        for (int i = 0; i < 26; i++) {
            if (bucket[i] > max && i != lastIndex) {
                max = bucket[i];
                index = i;
            }
        }
        return index;
    }
}

基于最大堆的贪心算法（跟我的想法相似，但是实现更好）

维护最大堆存储字母，堆顶元素为出现次数最多的字母。首先统计每个字母的出现次数，然后将出现次数大于 0 的字母加入最大堆。

当最大堆的元素个数大于 1 时，每次从最大堆取出两个字母，拼接到重构的字符串，然后将两个字母的出现次数分别减 1，并将剩余出现次数大于 0 的字母重新加入最大堆。由于最大堆中的元素都是不同的，因此取出的两个字母一定也是不同的，将两个不同的字母拼接到重构的字符串，可以确保相邻的字母都不相同。

如果最大堆变成空，则已经完成字符串的重构。如果最大堆剩下 1 个元素，则取出最后一个字母，拼接到重构的字符串。

对于长度为 n 的字符串，共有 n/2 次每次从最大堆取出两个字母的操作，当 n 是奇数时，还有一次从最大堆取出一个字母的操作，因此重构的字符串的长度一定是 n。

当 n 是奇数时，是否可能出现重构的字符串的最后两个字母相同的情况？如果最后一个字母在整个字符串中至少出现了 2 次，则在最后一次从最大堆取出两个字母时，该字母会先被选出，因此不会成为重构的字符串的倒数第二个字母，也不可能出现重构的字符串最后两个字母相同的情况。

因此，在重构字符串可行的情况下，基于最大堆的贪心算法可以确保得到正确答案。

class Solution {
    public String reorganizeString(String S) {
        if (S.length() < 2) {
            return S;
        }
        int[] counts = new int[26];
        int maxCount = 0;
        int length = S.length();
        for (int i = 0; i < length; i++) {
            char c = S.charAt(i);
            counts[c - 'a']++;
            maxCount = Math.max(maxCount, counts[c - 'a']);
        }
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        PriorityQueue<Character> queue = new PriorityQueue<Character>(new Comparator<Character>() {
            public int compare(Character letter1, Character letter2) {
                return counts[letter2 - 'a'] - counts[letter1 - 'a'];
            }
        });
        for (char c = 'a'; c <= 'z'; c++) {
            if (counts[c - 'a'] > 0) {
                queue.offer(c);
            }
        }
        StringBuffer sb = new StringBuffer();
        while (queue.size() > 1) {
            char letter1 = queue.poll();
            char letter2 = queue.poll();
            sb.append(letter1);
            sb.append(letter2);
            int index1 = letter1 - 'a', index2 = letter2 - 'a';
            counts[index1]--;
            counts[index2]--;
            if (counts[index1] > 0) {
                queue.offer(letter1);
            }
            if (counts[index2] > 0) {
                queue.offer(letter2);
            }
        }
        if (queue.size() > 0) {
            sb.append(queue.poll());
        }
        return sb.toString();
    }
}

class Solution {
    public String reorganizeString(String S) {
        if (S.length() < 2) {
            return S;
        }
        int[] counts = new int[26];
        int maxCount = 0;
        int length = S.length();
        for (int i = 0; i < length; i++) {
            char c = S.charAt(i);
            counts[c - 'a']++;
            maxCount = Math.max(maxCount, counts[c - 'a']);
        }
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        char[] reorganizeArray = new char[length];
        int evenIndex = 0, oddIndex = 1;
        int halfLength = length / 2;
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) {
                reorganizeArray[oddIndex] = c;
                counts[i]--;
                oddIndex += 2;
            }
            while (counts[i] > 0) {
                reorganizeArray[evenIndex] = c;
                counts[i]--;
                evenIndex += 2;
            }
        }
        return new String(reorganizeArray);
    }
}

参考文献

作者：LeetCode-Solution
链接：来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。