Formatted question description: https://leetcode.ca/all/767.html

767. Reorganize String (Medium)

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

 

Companies:
Google, Facebook, Amazon, Twitter

Related Topics:
String, Heap, Greedy, Sort

Similar Questions:

• Rearrange String k Distance Apart (Hard)
• Task Scheduler (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/reorganize-string/
// Time: O(NA) where A is the size of the alphabet
// Space: O(A)
class Solution {
public:
    string reorganizeString(string S) {
        int cnts[26] = {};
        for (char c : S) cnts[c - 'a']++;
        string ans(S.size(), '\0');
        for (int i = 0; i < S.size(); ++i) {
            int maxIndex = -1;
            for (int j = 0; j < 26; ++j) {
                if (!cnts[j] || (i > 0 && ans[i - 1] == j + 'a')) continue;
                if (maxIndex == -1 || cnts[j] > cnts[maxIndex]) maxIndex = j;
            }
            if (maxIndex == -1) return "";
            cnts[maxIndex]--;
            ans[i] = maxIndex + 'a';
        }
        return ans;
    }
};

Solution 2. Interleaving Placement

// OJ: https://leetcode.com/problems/reorganize-string/
// Time: O(AlogA + N) where A is the size of the alphabet 
// Space: O(A)
// Ref: https://leetcode.com/problems/reorganize-string/solution/
class Solution {
public:
    string reorganizeString(string S) {
        int N = S.size(), cnt[26] = {}, j = 1;
        for (char c : S) cnt[c - 'a'] += 100;
        for (int i = 0; i < 26; ++i) cnt[i] += i;
        sort(begin(cnt), end(cnt));
        string ans(N, ' ');
        for (int n : cnt) {
            int ct = n / 100, ch = n % 100;
            if (ct == 0) continue;
            if (ct > (N + 1) / 2) return "";
            while (ct--) {
                ans[j] = ch + 'a';
                j = (j + 2) % N;
                if (j == 1) j = 0;
            }
        }
        return ans;
    }
};

Solution 3. Greedy + Heap

// OJ: https://leetcode.com/problems/reorganize-string/
// Time: O(A + NlogA) where A is the size of the alphabet
// Space: O(A)
class Solution {
public:
    string reorganizeString(string S) {
        int cnt[26] = {}, prev = -1;
        for (char c : S) cnt[c - 'a']++;
        auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0; i < 26; ++i) if (cnt[i]) q.push(i);
        string ans;
        while (q.size()) {
            int c = q.top();
            q.pop();
            ans.push_back('a' + c);
            if (prev != -1) q.push(prev);
            if (--cnt[c]) prev = c;
            else prev = -1;
        }
        if (prev != -1) return "";
        return ans;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public String reorganizeString(String S) {
          if (S == null || S.length() < 2)
              return S;
          if (S.length() == 2)
              return S.charAt(0) == S.charAt(1) ? "" : S;
          int[] counts = new int[26];
          int maxCount = 0;
          int length = S.length();
          for (int i = 0; i < length; i++) {
              char c = S.charAt(i);
              counts[c - 'a']++;
              maxCount = Math.max(maxCount, counts[c - 'a']);
          }
          if (maxCount > (length + 1) / 2)
              return "";
          char[] reorganizeArray = new char[length];
          int evenIndex = 0, oddIndex = 1;
          int maxPossible = length / 2 + 1;
          for (int i = 0; i < 26; i++) {
              while (counts[i] > 0 && counts[i] < maxPossible && oddIndex < length) {
                  reorganizeArray[oddIndex] = (char) ('a' + i);
                  counts[i]--;
                  oddIndex += 2;
              }
              while (counts[i] > 0) {
                  reorganizeArray[evenIndex] = (char) ('a' + i);
                  counts[i]--;
                  evenIndex += 2;
              }
          }
          return new String(reorganizeArray);
      }
  }
  

• // OJ: https://leetcode.com/problems/reorganize-string/
  // Time: O(NA) where A is the size of the alphabet
  // Space: O(A)
  class Solution {
  public:
      string reorganizeString(string S) {
          int cnts[26] = {};
          for (char c : S) cnts[c - 'a']++;
          string ans(S.size(), '\0');
          for (int i = 0; i < S.size(); ++i) {
              int maxIndex = -1;
              for (int j = 0; j < 26; ++j) {
                  if (!cnts[j] || (i > 0 && ans[i - 1] == j + 'a')) continue;
                  if (maxIndex == -1 || cnts[j] > cnts[maxIndex]) maxIndex = j;
              }
              if (maxIndex == -1) return "";
              cnts[maxIndex]--;
              ans[i] = maxIndex + 'a';
          }
          return ans;
      }
  };
  

• class Solution(object):
      def reorganizeString(self, S):
          """
          :type S: str
          :rtype: str
          """
          counter = collections.Counter(S)
          ans = "#"
          while counter:
              stop = True
              for item, times in counter.most_common():
                  if ans[-1] != item:
                      ans += item
                      counter[item] -= 1
                      if not counter[item]:
                          del counter[item]
                      stop = False
                      break
              if stop: break
          return ans[1:] if len(ans) == len(S) + 1 else ""
  

All Problems

All Solutions