# 767. Reorganize String

![](/files/ESeFYM7tP2fRIawt9BKe)

## 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)

```java
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

```java
        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)

```java
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);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/767.-reorganize-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.