Skip to content

778. Reorganize String

Hash Table String Greedy Sorting Heap (Priority Queue) Counting

Problem - Reorganize String

Medium

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

 

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

 

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        count = Counter(s)
        highest_num = max(count.values())

        if highest_num > (n + 1)//2:
            return ""

        i = 0
        result = [None]*n
        for val, occurances in count.most_common():
            while occurances:
                result[i] = val
                occurances -= 1
                i += 2
                if i >= n:
                    i = 1
        return ''.join(result)

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.8 MB (47.23%)