767 Reorganize String

Given a stringS, 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:

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

Solution)

class Solution {
    public String reorganizeString(String S) {
        int n = S.length();
        int[] cnt = new int[128];
        char mc = 'a';
        for (char c : S.toCharArray()) {
            cnt[c]++;
            mc = (cnt[c] > cnt[mc]) ? c : mc;
        }
        if (cnt[mc] == 1) {
            return S;
        }
        if (n - cnt[mc] <= cnt[mc] - 2) {
            return "";
        }
        StringBuilder[] sb = new StringBuilder[cnt[mc]];
        for (int i = 0; i < sb.length; i ++) {
            sb[i] = new StringBuilder();
            sb[i].append(mc);
        }
        int k = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            while (c != mc && cnt[c] > 0) {
                sb[k++].append(c);
                cnt[c]--;
                k %= sb.length;
            }
        }
        for (int i = 1; i < sb.length; i++) {
            sb[0].append(sb[i]);
        }
        return sb[0].toString();
    }
}

If the number of one character is more than (half-length +1) of the entire string, no possible result. Otherwise, we just need to fill the same character to string in even slot first, and then odd slot, to make sure the same character won’t meet. One special case is when the number of one character is exactly half length + 1. Then we need to put this character in the odd slot only.

public String reorganizeString(String S) {
        int n=S.length();
        if(n<=1) return S;
        int[] str = new int[26];
        int hf=0;
        for(char a: S.toCharArray()){
            if(hf<++str[a-'a']) hf=str[a-'a'];
        }
        if(hf*2-1>n) return "";
        char[] res=new char[n];
        int odd=0, even=1;
        for(int i=0;i<26;i++){
            while(str[i]>0 && str[i]<n/2+1 && even<n){
                res[even]= (char)(i+'a');
                even+=2;
                str[i]--;
            }
            while(str[i]>0){
                res[odd]=(char)(i+'a');
                odd+=2;
                str[i]--;
            }
        }
        return new String(res);
    }

class Solution {
    public String reorganizeString(String S) {
      if (S.length() < 2) return S;
      Map<Character, Integer> map = new HashMap<>();
      for (char c : S.toCharArray()) {
          int count = map.getOrDefault(c, 0) + 1;
          if (count > (S.length()+1)/2) return "";
          map.put(c, count);
      }
      PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[1] - a[1]));
      for (char c : map.keySet())
          pq.add(new int[]{c, map.get(c)});

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