[LeetCode] 767. Reorganize String

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Note:

• S will consist of lowercase letters and have length in range [1, 500].

重构字符串。

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。若可行，输出任意可行的结果。若不可行，返回空字符串。影子题358。思路是priority queue + hashmap。hashmap存的是每个字符和他们出现的次数；priority queue存的是hashmap的entry，但是是一个按照字符出现次数来排序的一个maxheap，也就是说出现次数越多的字符会在heap顶端。先遍历一遍input，存入字符和他们各自出现的次数之后，也同时把每个hashmap entry存入pq。有一个corner cases是，在遍历input字符串的时候，如果有任何一个字符的出现次数大于input的一半则返回空字符串，因为一定无法满足题意。corner case处理完之后就开始从pq往外弹出元素。先弹出一个，记为first，判断如果上一个被attach的字符也是first的话则再弹出一个second字符。加了哪个字符，就对其mapvalue--并判断是否需要再加回maxheap，直到pq为空。

时间O(nlogn)

空间O(n)

Java实现

class Solution {
    public String reorganizeString(String S) {
        // Create map of each char to its count
        Map<Character, Integer> map = new HashMap<>();
        for (char c : S.toCharArray()) {
            int count = map.getOrDefault(c, 0) + 1;
            // Impossible to form a solution
            if (count > (S.length() + 1) / 2) {
                return "";
            }
            map.put(c, count);
        }
        // Greedy: fetch char of max count as next char in the result.
        // Use PriorityQueue to store pairs of (char, count) and sort by count DESC.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (char c : map.keySet()) {
            pq.add(new int[] { c, map.get(c) });
        }
        // Build the result.
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (sb.length() == 0 || first[0] != sb.charAt(sb.length() - 1)) {
                sb.append((char) first[0]);
                if (--first[1] > 0) {
                    pq.add(first);
                }
            } else {
                int[] second = pq.poll();
                sb.append((char) second[0]);
                if (--second[1] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }
        return sb.toString();
    }
}

另一种做法是创建一个hashmap先记录每个字母出现的频率，再创建一个跟input字符串等长的数组开始往里面放字母。首先放出现次数最多的字母，并且放的时候，每两个字母之间隔开一个位置，类似[0, 2, 4, 6...]这样的放置方法。出现次数最多的字母处理完之后，其他的字母也是隔开一个位置这样的方式，放入数组剩下的位置里面。为什么出现次数最多的字母是一个比较特殊的情形是因为最极端的情况，出现次数最多的字母有可能占据input长度的一半。

时间O(n)

空间O(n)

Java实现

class Solution {
    public String reorganizeString(String S) {
        int[] hash = new int[26];
        for (int i = 0; i < S.length(); i++) {
            hash[S.charAt(i) - 'a']++;
        }
        int max = 0;
        int letter = 0;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
        // corner case
        if (max > (S.length() + 1) / 2) {
            return "";
        }
        char[] res = new char[S.length()];
        int index = 0;
        while (hash[letter] > 0) {
            res[index] = (char) (letter + 'a');
            index += 2;
            hash[letter]--;
        }
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] > 0) {
                if (index >= res.length) {
                    index = 1;
                }
                res[index] = (char) (i + 'a');
                index += 2;
                hash[i]--;
            }
        }
        return String.valueOf(res);
    }
}

相关题目

358. Rearrange String k Distance Apart

767. Reorganize String

LeetCode 题目总结