重构字符串

2021-01-02

重构字符串（日常刷题记录）

题目链接：https://leetcode-cn.com/problems/reorganize-string/

用搜索，超时了。

class Solution {
    String ans = "";
    public String reorganizeString(String S) {
        int len = S.length();
        if(len == 0){
            return "";
        }
        int maps[] = new int[26];
        char ch[] = S.toCharArray();
        HashSet<Character> sets = new HashSet<>();
        for(int i = 0; i < len; i++){
            sets.add(ch[i]);
            maps[ch[i] - 'a']++;
        }
        dfs("", maps, sets, len);
        return ans;
    }
    public void dfs(String tmp, int maps[], Set<Character> sets, int len){
        if (tmp.length() == len){
            ans = tmp;
            return ;
        }
        for (Character c:sets){
            if (maps[c - 'a'] <= 0){
                continue;
            }
            if (tmp.equals("") || tmp.charAt(tmp.length() - 1) != c){
                maps[c - 'a']--;
                dfs(tmp + c, maps, sets, len);
                maps[c - 'a']++;
            }
        }

    }

}

看了题解，emmmmm，贪心可以解，还能用堆？

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

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

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

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

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

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

如果一个字母出现了多次，则重复上述操作，直到该字母全部放置完毕。

那么上述做法是否可以确保相邻的字母都不相同？考虑以下三种情况。

如果 $n$ 是奇数且存在一个字母的出现次数为 $(n+1)/2$ ，则该字母全部被放置在偶数下标，其余的 $(n-1)/2$个字母都被放置在奇数下标，因此相邻的字母一定不相同。比如：”aaaabbc”。
如果同一个字母全部被放置在奇数下标或全部被放置在偶数下标，则该字母不可能在相邻的下标出现。
如果同一个字母先被放置在奇数下标直到奇数下标超出数组下标范围，然后被放置在偶数下标，由于该字母的出现次数不会超过 $n/2$，因此该字母的最小奇数下标与最大偶数下标之差不小于 $3$，不可能在相邻的下标出现。

证明如下：
- 当 $n$ 是偶数时，如果该字母的出现次数为 $n/2$，包括 $p$ 个奇数下标和 $q$ 个偶数下标，满足 $p+q=n/2$，最小奇数下标是 $n-2p+1$，最大偶数下标是 $2(q-1)$，最小奇数下标与最大偶数下标之差为：

当 $n$ 是奇数时，如果该字母的出现次数为 $(n-1)/2$，包括 $p$ 个奇数下标和 $q$ 个偶数下标，满足 $p+q=(n-1)/2$，最小奇数下标是 $n-2p$，最大偶数下标是 $2(q-1)$，最小奇数下标与最大偶数下标之差为：

$\begin{aligned} & (n-2p)-2(q-1) \\ = &\ n-2p-2q+2 \\ = &\ n-2(p+q)+2 \\ = &\ n-2 \times \frac{n-1}{2}+2 \\ = &\ n-(n-1)+2 \\ = &\ 3 \end{aligned}$

空间复杂度：$O(|\Sigma|)$。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public String reorganizeString(String S) {
        int len = S.length();
        if(len == 0){
            return "";
        }
        int maps[] = new int[26], max_freq = 1;
        char ch[] = S.toCharArray();
        HashSet<Character> sets = new HashSet<>();
        for(int i = 0; i < len; i++){
            sets.add(ch[i]);
            maps[ch[i] - 'a']++;
            if (maps[ch[i] - 'a'] > max_freq){
                max_freq = maps[ch[i] - 'a'];
            }
        }
        if (len % 2 == 0 && max_freq > len / 2 || len % 2 == 1 && max_freq > len / 2 + 1){
            return "";
        }
        char res[] = new char[len];
        int evenIndex = 0, oddIndex = 1;
        // 按照每个字母的出现频率放置字母
        for (int i = 0; i < maps.length; i++){

            if (maps[i] > 0 && maps[i] <= len / 2 ){
                while (maps[i] > 0 && maps[i] <= len / 2 && oddIndex < len){
                    res[oddIndex] = (char)('a' + i);
                    maps[i]--;
                    oddIndex += 2;
                }

            }
            if (maps[i] > len / 2 || oddIndex >= len){
                while (maps[i] > 0 && evenIndex < len){
                    res[evenIndex] = (char)('a' + i);
                    maps[i]--;
                    evenIndex += 2;
                }
            }
        }
        return String.valueOf(res);
    }
}