Skip to content

767. Reorganize String 👍

Approach 1: Heap

  • Time: $O(n\log 26) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 letter with the maximum frequency.
      const auto [freq, c] = maxHeap.top();
      maxHeap.pop();
      ans += c;
      // Add the previous letter back s.t. any two adjacent characters are not
      // the same.
      if (prevFreq > 0)
        maxHeap.emplace(prevFreq, prevChar);
      prevFreq = freq - 1;
      prevChar = c;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public String reorganizeString(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int maxFreq = 0;

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

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

    StringBuilder sb = new StringBuilder();
    // (freq, c)
    Queue<Pair<Integer, Character>> maxHeap =
        new PriorityQueue<>((a, b) -> b.getKey().compareTo(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 letter with the maximum frequency.
      final int freq = maxHeap.peek().getKey();
      final char c = maxHeap.poll().getValue();
      sb.append(c);
      // Add the previous letter back s.t. 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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def reorganizeString(self, s: str) -> str:
    count = collections.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 letter with the maximum frequency.
      freq, c = heapq.heappop(maxHeap)
      ans.append(c)
      # Add the previous letter back s.t. 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)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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' index

    auto fillIn = [&](char c) {
      ans[i] = c;
      i += 2;
      if (i >= n)
        i = 1;
    };

    // Fill in 0, 2, 4, ... indices with `maxCount` letters.
    while (count[maxChar]-- > 0)
      fillIn(maxChar);

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

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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 `maxCount` letters.
    while (count[maxChar]-- > 0)
      fillIn(ans, maxChar);

    // Fill in the remaining letters.
    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' index

  private void fillIn(char[] ans, char c) {
    ans[i] = c;
    i += 2;
    if (i >= ans.length)
      i = 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def reorganizeString(self, s: str) -> str:
    n = len(s)
    count = collections.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)