767. Reorganize String

Approach 1: Heap

• Time: $O(n\log 26) = O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string reorganizeString(string s) {
    unordered_map<char, int> count;
    int maxFreq = 0;

    for (const char c : s)
      maxFreq = max(maxFreq, ++count[c]);

    if (maxFreq > (s.length() + 1) / 2)
      return "";

    string ans;
    priority_queue<pair<int, char>> maxHeap;  // (freq, c)
    int prevFreq = 0;
    char prevChar = '@';

    for (const auto& [c, freq] : count)
      maxHeap.emplace(freq, c);

    while (!maxHeap.empty()) {
      // get the most freq letter
      const auto [freq, c] = maxHeap.top();
      maxHeap.pop();
      ans += c;
      // add the previous letter back so that
      // any two adjacent characters are not the same
      if (prevFreq > 0)
        maxHeap.emplace(prevFreq, prevChar);
      prevFreq = freq - 1;
      prevChar = c;
    }

    return ans;
  }
};

public class Solution {
  public String reorganizeString(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int maxFreq = 0;

    for (final char c : s.toCharArray()) {
      count.merge(c, 1, Integer::sum);
      maxFreq = Math.max(maxFreq, count.get(c));
    }

    if (maxFreq > (s.length() + 1) / 2)
      return "";

    StringBuilder sb = new StringBuilder();
    // (freq, c)
    Queue<Pair<Integer, Character>> maxHeap =
        new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
    int prevFreq = 0;
    char prevChar = '@';

    for (final char c : count.keySet())
      maxHeap.offer(new Pair<>(count.get(c), c));

    while (!maxHeap.isEmpty()) {
      // get the most freq letter
      final int freq = maxHeap.peek().getKey();
      final char c = maxHeap.poll().getValue();
      sb.append(c);
      // add the previous letter back so that
      // any two adjacent characters are not the same
      if (prevFreq > 0)
        maxHeap.offer(new Pair<>(prevFreq, prevChar));
      prevFreq = freq - 1;
      prevChar = c;
    }

    return sb.toString();
  }
}

class Solution:
  def reorganizeString(self, s: str) -> str:
    count = Counter(s)
    if max(count.values()) > (len(s) + 1) // 2:
      return ''

    ans = []
    maxHeap = [(-freq, c) for c, freq in count.items()]
    heapq.heapify(maxHeap)
    prevFreq = 0
    prevChar = '@'

    while maxHeap:
      # get the most freq letter
      freq, c = heapq.heappop(maxHeap)
      ans.append(c)
      # add the previous letter back so that
      # any two adjacent characters are not the same
      if prevFreq < 0:
        heapq.heappush(maxHeap, (prevFreq, prevChar))
      prevFreq = freq + 1
      prevChar = c

    return ''.join(ans)

Approach 2: Bucket

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string reorganizeString(string s) {
    const int n = s.length();
    vector<int> count(128);
    char maxChar = 'a' - 1;

    for (const char c : s)
      ++count[c];

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c] > count[maxChar])
        maxChar = c;

    if (count[maxChar] > (n + 1) / 2)
      return "";

    string ans(n, ' ');
    int i = 0;  // ans's index

    auto fillIn = [&](char c) {
      ans[i] = c;
      i += 2;
      if (i >= n)  // out of bound, reset the index to 1
        i = 1;
    };

    // fill in 0, 2, 4, ... indices with the maxCount char
    while (count[maxChar]-- > 0)
      fillIn(maxChar);

    // fill in remaining characters
    for (char c = 'a'; c <= 'z'; ++c)
      while (count[c] > 0) {
        --count[c];
        fillIn(c);
      }

    return ans;
  }
};

class Solution {
  public String reorganizeString(String s) {
    final int n = s.length();

    int[] count = new int[128];
    char maxChar = 'a' - 1;

    for (final char c : s.toCharArray())
      ++count[c];

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c] > count[maxChar])
        maxChar = c;

    if (count[maxChar] > (n + 1) / 2)
      return "";

    char[] ans = new char[n];

    // fill in 0, 2, 4, ... indices with the maxCount char
    while (count[maxChar]-- > 0)
      fillIn(ans, maxChar);

    // fill in remaining characters
    for (char c = 'a'; c <= 'z'; ++c)
      while (count[c] > 0) {
        --count[c];
        fillIn(ans, c);
      }

    return new String(ans);
  }

  private int i = 0; // ans's index

  private void fillIn(char[] ans, char c) {
    ans[i] = c;
    i += 2;
    if (i >= ans.length) // out of bound, reset the index to 1
      i = 1;
  }
}

class Solution:
  def reorganizeString(self, s: str) -> str:
    n = len(s)
    count = Counter(s)
    maxCount = max(count.values())

    if maxCount > (n + 1) // 2:
      return ''

    if maxCount == (n + 1) // 2:
      maxLetter = max(count, key=count.get)
      ans = [maxLetter if i % 2 == 0 else '' for i in range(n)]
      del count[maxLetter]
      i = 1
    else:
      ans = [''] * n
      i = 0

    for c, freq in count.items():
      for _ in range(freq):
        ans[i] = c
        i += 2
        if i >= n:
          i = 1

    return ''.join(ans)