767. Reorganize String

greedy

put most high freq first

ex: aaaaabbbbc

a_a_a_a_a_____

then put b into empty slot, then c

so the insert index is start at 0, but +=2,

if ( index > s.length), index = 1, to fill empty slot

fail case in Reorganize String

1. if the highest freq is bigger than s.length/2, you cant complete the new String, return "";

2. or just check if (i >= 1 && newStr[i] == newStr[i-1]), means cant reorganinze, return "";

time: O(n + klogk), n is String s length, k is the list<Pair> length

space: O(k), use map to keep freq, k is the kind of char, List<Pair> space is also O(k)

class Solution {
    class Pair {
        int freq;
        char c;
        Pair(int freq, char c) {
            this.freq = freq;
            this.c = c;
        }
    }
    public String reorganizeString(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) +1);
        }
        
        List<Pair> list = new ArrayList<>();
        for (Character c : map.keySet()) {
            list.add(new Pair(map.get(c), c));
        }
        Collections.sort(list, (a, b) -> b.freq - a.freq);
        
        char res[] = new char[s.length()];
        
        int i = 0;
        for (Pair pair : list) {
            while (pair.freq > 0) {
                System.out.println("i:" + i);
                System.out.println("freq:" + pair.freq);
                System.out.println("c:" + pair.c);
                res[i] = pair.c;
                if (i >= 1 && res[i] == res[i-1]) {
                    return "";
                }
                i+=2;
                if (i >= s.length()) {
                    i = 1;
                }
                pair.freq--;
            }
        }
        return String.valueOf(res);   
        
    }
}

use array map

        int map[] = new int[26];
        for (char c : s.toCharArray()) {
            map[c-'a']++;
        }
        
        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            list.add(new Pair(map[i], (char) (i+'a')));
        }

this is the fastest

T: O(n), n is s len

S: O(26 + n)

class Solution {
    public String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c-'a']++;
        }
        
        // only need the most freq one
        int mostFreq = 0;
        int letterIdx = 0;
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > mostFreq) {
                mostFreq = freq[i];
                letterIdx = i;
            }
        }
        
        // all empty result can handle here
        // aab, mostFreq = 2, 2 > 4/2 = 2 , no, so dont ""
        // aab => aba
        if (mostFreq > (s.length()+1) / 2) {
            return ""; 
        }
        
        // put most first, from index 0, 間隔 2
        char[] res = new char[s.length()];
        int idx = 0;
        while (freq[letterIdx] > 0) {
            res[idx] = (char)(letterIdx+'a');
            idx += 2;
            freq[letterIdx]--;
        }

        // put others, when idx >= s.len, start from index 1, 間隔 2
        for (int i = 0; i < freq.length; i++) {
            while (freq[i] > 0) {
                if (idx >= s.length()) {
                    idx = 1;
                }
                res[idx] = (char)(i+'a');
                // if (idx >= 1 && res[idx] == res[idx-1]) {
                //     return "";
                // }
                idx+= 2;
                freq[i]--;
            }
        }
        return String.valueOf(res);
    }
}