MediumNo. 0767
Reorganize String — LeetCode 767 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Hash Table, String, Counting, Sorting, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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
- Input
- s = "aab"
- Output
- "aba"
Python solution
class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
cnt = Counter(s)
mx = max(cnt.values())
if mx > (n + 1) // 2:
return ''
i = 0
ans = [None] * n
for k, v in cnt.most_common():
while v:
ans[i] = k
v -= 1
i += 2
if i >= n:
i = 1
return ''.join(ans)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 767. Reorganize String is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0451 | Sort Characters By Frequency | Medium |
| 0621 | Task Scheduler | Medium |
| 0692 | Top K Frequent Words | Medium |
| 1054 | Distant Barcodes | Medium |
| 2182 | Construct String With Repeat Limit | Medium |
| 0347 | Top K Frequent Elements | Medium |
Frequently asked questions
- How hard is LeetCode 767. Reorganize String?
LeetCode 767. Reorganize String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 767. Reorganize String?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 767. Reorganize String?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 767. Reorganize String cover?
LeetCode 767. Reorganize String is tagged Greedy, Hash Table, String, Counting, Sorting and Heap (Priority Queue) on LeetCode.