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 <= 500s consists of lowercase English letters.
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
|
class Solution:
def reorganizeString(self, s: str) -> str:
counts = [0] * 26
most_common_char = 0
most_common_count = 0
for c in s:
idx = ord(c) - ord('a')
counts[idx] += 1
if counts[idx] > most_common_count:
most_common_char = c
most_common_count = counts[idx]
sub_chars = [most_common_char] * most_common_count
rest = ''
for i in range(26):
char = chr(i + ord('a'))
if char == most_common_char:
continue
rest += (char * counts[i])
if len(rest) < most_common_count - 1:
return ''
i = 0
for c in rest:
sub_chars[i] += c
i = (i + 1) % most_common_count
return ''.join(sub_chars)
|