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.
https://leetcode.com/problems/reorganize-string/
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
Constraints:
1 <= s.length <= 500s consists of lowercase English letters.
Test Cases
1
2
| class Solution:
def reorganizeString(self, s: str) -> str:
|
solution_test.py1
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
| import pytest
from solution import Solution
def verify(res, s):
assert sorted(res) == sorted(s)
prev = res[0]
for i in range(1, len(s)):
assert prev != res[i]
prev = res[i]
@pytest.mark.parametrize('s, expected', [
("aab", "aba"),
("aaab", ""),
("vvvlo", "vlvov"),
("aabbcc", "abacbc"),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
res = sol.reorganizeString(s)
if expected == '':
assert res == ''
else:
assert res != ''
if res != expected:
verify(res, s)
|
Thoughts
判定是否可行很简单，显然如果有一个字符的出现次数大于 ⌈n/2⌉ 就不可行，否则可行。
开始以为重新排列 s 的逻辑类似于 2182. Construct String With Repeat Limit，相当于 repeatLimit = 1，且不限定字符的顺序。但是因为要求是用掉所有的字符（当可行的时候），重建的逻辑就还是会有些不同。Problem 2182 中因为要让结果字符串按字典序最大，每次都先取最大的字符，却并不保证所有字符都能用上。
本题需要把所有的字符都用上，可以考虑建一个词频的最大堆（词频相同时按字符的字典序），每次从堆中取出词频最大的两个字符，添加到结果字符串末尾。把两个字符以及剩余的词频（如果还大于零）放回到堆中。因为词频相同的字符会按字典序排序，本次取出的第二个字符一定不会跟下一次取出的第一个字符相同，不会产生连续重复字符。
最后如果堆里只剩下一个字符（显然剩余的词频只能是 1），将其加到结果字符串的末尾即可。
时间复杂度 O(n log C)，空间复杂度 O(C)，其中 C 是 s 中各不相同的字符总数，题目中 C ≤ 26 可以认为是常数。
Code
solution.py1
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
| from heapq import heapify, heappop, heappush, heapreplace
from typing import Counter
class Solution:
def reorganizeString(self, s: str) -> str:
counts = Counter(s)
if max(counts.values()) > ((len(s) + 1) >> 1):
return ''
parts = []
queue = [(-f, c) for c, f in counts.items()]
heapify(queue)
while len(queue) > 1:
f1, c1 = heappop(queue)
f2, c2 = queue[0]
parts.append(c1)
parts.append(c2)
f1 += 1
f2 += 1
if f2:
heapreplace(queue, (f2, c2))
heappush(queue, (f1, c1))
elif f1:
heapreplace(queue, (f1, c1))
else:
heappop(queue)
if queue:
parts.append(queue[0][1])
return ''.join(parts)
|
