767. 重构字符串

Desciption

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。 若可行，输出任意可行的结果。若不可行，返回空字符串。 示例:

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

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

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

Solution

贪心，构造

  • 假设字符串的长度为n，只要某个字符出现次数超过 (n + 1) / 2，则输出""；想了一下，剩下的情况是一定能够构造出结果的

  • 接下来考虑一下怎么构造，想到一种构造方案 1. 统计每个字符出现次数并放进优先队列，按次数从大到小排序 2. 先构造奇数位置的字符，从优先队列取出出现次数最多的字符，在该奇数位放入该字符后，字符次数减一并重新push进队列，一直构造 (n + 1) / 2 个位置 3. 按照第2步的方法继续构造偶数位

  • 上面的方法有反例：vvvlo，当第1、3两个字符为v之后，第5个字符队列里取出来的不确定，会导致第三个v会和前面两个v相邻。考虑一种更为简单的构造：

    1. 取出出现次数最多的字符，然后从第0个位置，把它隔着一位全部放完，接下来再找出出现次数最多的字符，接着上次的地方继续放
    2. 当长度超过n之后，从第1个位置开始放，直到放完所有字符，就是一个可行的答案

Code

    public String reorganizeString(String S) {
        int n = S.length();
        int[] countArr = new int[26];
        Arrays.fill(countArr, 0);
        for (int i = 0; i < n; ++i) {
            int val = S.charAt(i) - 'a';
            countArr[val]++;
            if (countArr[val] > (n + 1) / 2) {
                return "";
            }
        }

        char[] res = new char[n];
        int len = 0, cur = 0;
        while (len < n) {
            int pos = 0;
            for (int i = 0; i < 26; ++i) {
                if (countArr[i] > countArr[pos]) {
                    pos = i;
                }
            }
            for (int i = 0; i < countArr[pos]; ++i) {
                res[cur] = (char)(pos + 'a');
                cur += 2;
                if (cur >= n) {
                    cur = 1;
                }
            }
            len += countArr[pos];
            countArr[pos] = 0;
        }

        return String.valueOf(res);
    }