0767. Reorganize String

https://leetcode.com/problems/reorganize-string

Description

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

**Input:** s = "aab"
**Output:** "aba"

Example 2:

**Input:** s = "aaab"
**Output:** ""

Constraints:

• 1 <= s.length <= 500

• s consists of lowercase English letters.

ac

It's kinda tricky problem. Maybe solution is not general for other problems.

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

class Solution {
    public String reorganizeString(String s) {
        // Edge cases
        if (s == null || s.length() == 0) {
            return s;
        }
        
        int[] count = new int[26];
        int topFrequency = 0;
        char topFrequencyChar = 'a';
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            count[idx]++;
            if (count[idx] > topFrequency) {
                topFrequency = count[idx];
                topFrequencyChar = s.charAt(i);
            }
        }
        
        // Invalid case: the most frequent char can't be placed in the result string.
        // Given length N, you can at most place (N+1)/2 repeated char to make them not adjacent.
        if ((s.length() + 1) / 2 < topFrequency) return "";
        
        char[] res = new char[s.length()];
        int index = 0;
        while (topFrequency > 0) {
            res[index] = topFrequencyChar;
            index += 2;
            topFrequency--;
        }
        
        for (int i = 0; i < count.length; i++) {
            if (count[i] == 0 || topFrequencyChar == (char)('a'+i)) continue;
            while (count[i] > 0) {
                if (index >= res.length) index = 1;
                res[index] = (char)('a'+i);
                count[i]--;
                index += 2;
            }
        }
        
        return new String(res);
    }
}
// O(N) time, O(N) space