LeetCode 767 - Reorganize String

Related:
LeetCode 358 - Rearrange String k Distance Apart
LeetCode 767 - Reorganize String
LeetCode 621 - Task Scheduler
https://leetcode.com/problems/reorganize-string/solution/

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].

We store a heap of (count, letter). [In Python, our implementation stores negative counts.]

We pop the top two elements from the heap (representing different letters with positive remaining count), and then write the most frequent one that isn't the same as the most recent one written. After, we push the correct counts back onto the heap.

Actually, we don't even need to keep track of the most recent one written. If it is possible to organize the string, the letter written second can never be written first in the very next writing.

At the end, we might have one element still on the heap, which must have a count of one. If we do, we'll add that to the answer too.

• Time Complexity: $O(N \log{\mathcal{A}}))$, where $N$ is the length of $S$, and $\mathcal{A}$ is the size of the alphabet. If $\mathcal{A}$ is fixed, this complexity is $O(N)$.
• Space Complexity: $O(\mathcal{A})$. If $\mathcal{A}$ is fixed, this complexity is $O(1)$.

优先队列这种方式应该是比较容易就能想到，其他思路可能需要对这个题目有更深的理解。优先队列这种数据结构还是很好用的，在做题中好好使用吧。

https://leetcode.com/problems/reorganize-string/discuss/113427/C++-Greedy-sort-O(N)

  public String reorganizeString(String S) {

    int N = S.length();

    int[] count = new int[26];

    for (char c : S.toCharArray())

      count[c - 'a']++;

    PriorityQueue<MultiChar> pq = new PriorityQueue<MultiChar>(

        (a, b) -> a.count == b.count ? a.letter - b.letter : b.count - a.count);

    for (int i = 0; i < 26; ++i)

      if (count[i] > 0) {

        if (count[i] > (N + 1) / 2)

          return "";

        pq.add(new MultiChar(count[i], (char) ('a' + i)));

      }

    StringBuilder ans = new StringBuilder();

    while (pq.size() >= 2) {

      MultiChar mc1 = pq.poll();

      MultiChar mc2 = pq.poll();

      /*

       * This code turns out to be superfluous, but explains what is happening if

       * (ans.length() == 0 || mc1.letter != ans.charAt(ans.length() - 1)) {

       * ans.append(mc1.letter); ans.append(mc2.letter); } else {

       * ans.append(mc2.letter); ans.append(mc1.letter); }

       */

      ans.append(mc1.letter);

      ans.append(mc2.letter);

      if (--mc1.count > 0)

        pq.add(mc1);

      if (--mc2.count > 0)

        pq.add(mc2);

    }

    if (pq.size() > 0)

      ans.append(pq.poll().letter);

    return ans.toString();

  }

}

class MultiChar {

  int count;

  char letter;

  MultiChar(int ct, char ch) {

    count = ct;

    letter = ch;

  }

}

https://leetcode.com/problems/reorganize-string/discuss/113440/Java-solution-PriorityQueue

    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();
    }




X.http://www.cnblogs.com/grandyang/p/8799483.html

下面这种解法的原理和上面的很类似，就是写法上很秀，堪比陈独秀。这里使用了一个长度为26的一位数组cnt来代替上面的HashMap进行统计字母的出现次数，然后比较秀的一点是，把上面的映射对儿压缩成了一个整数，做法是将次数乘以了100，再加上当前字母在一位数字中的位置坐标i，这样一个整数就同时encode了次数和对应字母的信息了，而且之后decode也很方便。数组cnt更新好了后，需要排个序，这一步就是模拟上面解法中最大堆的自动排序功能。不过这里是数字小的在前面，即先处理出现次数少的字母。这里除了和上面一样检测次数不能大于总长度的一半的操作外，还有一个小trick，就是构建字符串的时候，是从第二个位置开始的。这里我们构建的字符串是直接对原字符串S进行修改的，因为cnt数组建立了之后，字符串S就没啥用了。我们用一个变量idx来表示当前更新字母的位置，初始化为1，表示我们要从第二个位置开始更新。因为出现次数最多的字母一定要占据第一个位置才行，这就是我们留出第一个位置的原因。这里很叼的一点，就是隔位更新，这样能保证相同的字母不相邻，而且当idx越界后，拉回到起始位置0，这就有点遍历循环数组的感觉。举个栗子来说吧，比如"aaabbc"，我们的更新顺序为：

_ c _ _ _ _

_ c _ b _ _

_ c _ b _ b

a c _ b _ b

a c a b _ b

a c a b a b

    string reorganizeString(string S) {
        int n = S.size(), idx = 1;
        vector<int> cnt(26, 0);
        for (char c : S) cnt[c - 'a'] += 100;
        for (int i = 0; i < 26; ++i) cnt[i] += i;
        sort(cnt.begin(), cnt.end());
        for (int num : cnt) {
            int t = num / 100;
            char ch = 'a' + (num % 100);
            if (t > (n + 1) / 2) return "";
            for (int i = 0; i < t; ++i) {
                if (idx >= n) idx = 0;
                S[idx] = ch;
                idx += 2;
            }
        }
        return S;
    }

If we should make no two 'a's adjacent, it is natural to write "aXaXaXa..." where "X" is some letter. For now, let's assume that the task is possible (ie. the answer is not "".)

Let's sort the string S, so all of the same kind of letter occur in continuous blocks. Then when writing in the following interleaving pattern, like S[3], S[0], S[4], S[1], S[5], S[2], adjacent letters never touch. (The specific interleaving pattern is that we start writing at index 1 and step by 2; then start from index 0 and step by 2.)

The exception to this rule is if N is odd, and then when interleaving like S[2], S[0], S[3], S[1], S[4], we might fail incorrectly if there is a block of the same 3 letters starting at S[0] or S[1]. To prevent failing erroneously in this case, we need to make sure that the most common letters all occur at the end.

Finally, it is easy to see that if N is the length of the string, and the count of some letter is greater than (N+1) / 2, the task is impossible.

Algorithm

Find the count of each character, and use it to sort the string by count.

If at some point the number of occurrences of some character is greater than (N + 1) / 2, the task is impossible.

Otherwise, interleave the characters in the order described above.

• Time Complexity: $O(\mathcal{A}(N + \log{\mathcal{A}}))$, where $N$ is the length of $S$, and $\mathcal{A}$ is the size of the alphabet. In Java, our implementation is $O(N + \mathcal{A} \log {\mathcal{A}})$. If $\mathcal{A}$ is fixed, this complexity is $O(N)$.
• Space Complexity: $O(N)$. In Java, our implementation is $O(N + \mathcal{A})$.

  public String reorganizeString(String S) {

    int N = S.length();

    int[] counts = new int[26];

    for (char c : S.toCharArray())

      counts[c - 'a'] += 100;

    for (int i = 0; i < 26; ++i)

      counts[i] += i;

    // Encoded counts[i] = 100*(actual count) + (i)

    Arrays.sort(counts);

    char[] ans = new char[N];

    int t = 1;

    for (int code : counts) {

      int ct = code / 100;

      char ch = (char) ('a' + (code % 100));

      if (ct > (N + 1) / 2)

        return "";

      for (int i = 0; i < ct; ++i) {

        if (t >= N)

          t = 0;

        ans[t] = ch;

        t += 2;

      }

    }

    return String.valueOf(ans);

  }

X. https://leetcode.com/problems/reorganize-string/discuss/232469/Java-O(N)-3ms-beat-100

No Sort O(N):

1. count letter appearance and store in hash[i]
2. find the letter with largest occurence.
3. put the letter into even index numbe (0, 2, 4 ...) char array
4. put the rest into the array

    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, letter = 0;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
        if (max > (S.length() + 1) / 2) {
            return ""; 
        }
        char[] res = new char[S.length()];
        int idx = 0;
        while (hash[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            hash[letter]--;
        }
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] > 0) {
                if (idx >= res.length) {
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                idx += 2;
                hash[i]--;
            }
        }
        return String.valueOf(res);
    }

Time O(N): fill hash[] + find the letter + write results into char array
Space O(N + 26): result + hash[]

https://zhuanlan.zhihu.com/p/33231348

在题目讨论区还存在一种不使用优先队列的方法。思路如下：首先找出字符数量最大的字符，如果大于S长度的一半，返回空字符串，如果小于，则将该字符从索引0开始，间隔着放置(0, 2, 4...)。然后再放其他字符，

如果偶数索引没有放完，则接着间隔着放，如果偶数索引结束了，则从索引1开始(1, 3, 5...)。

这个题目首先要判断出不能重组的条件，做之前没有想到这点，所以做的思路不是很清晰。

public String reorganizeString(String S) {
    char ch[] = new char[26];
    int max = 0;
    for(char c: S.toCharArray()) {
        ch[c - 'a'] ++;
        if(ch[c-'a'] > ch[max]) max = c - 'a';
    }
    int len = S.length();
    if(len < 2 * ch[max] - 1) return "";
    int index = 0;
    char []res = new char[len];
    for(int i = 0 ; i < ch[max]; i++) {
        res[index] = (char)(max + 'a');
        index += 2;
    }
    ch[max] = 0;
    for(int i = 0 ; i < 26; i++) {
        int count = ch[i];
        while(count > 0 ) {
            if(index >= len ) index = 1;
            res[index] = (char)(i + 'a');
            index += 2;
            count --;
        }
    }

    return new String(res);
}