Greedy
Hash Table
String
Counting
Sorting
Heap (Priority Queue)
Description
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
Solution 1
Python3 Java C++ Go Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 )
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
42 class Solution {
public String reorganizeString ( String s ) {
int [] cnt = new int [ 26 ] ;
int mx = 0 ;
for ( char c : s . toCharArray ()) {
int t = c - 'a' ;
++ cnt [ t ] ;
mx = Math . max ( mx , cnt [ t ] );
}
int n = s . length ();
if ( mx > ( n + 1 ) / 2 ) {
return "" ;
}
int k = 0 ;
for ( int v : cnt ) {
if ( v > 0 ) {
++ k ;
}
}
int [][] m = new int [ k ][ 2 ] ;
k = 0 ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > 0 ) {
m [ k ++] = new int [] { cnt [ i ] , i };
}
}
Arrays . sort ( m , ( a , b ) -> b [ 0 ] - a [ 0 ] );
k = 0 ;
StringBuilder ans = new StringBuilder ( s );
for ( int [] e : m ) {
int v = e [ 0 ] , i = e [ 1 ] ;
while ( v -- > 0 ) {
ans . setCharAt ( k , ( char ) ( 'a' + i ));
k += 2 ;
if ( k >= n ) {
k = 1 ;
}
}
}
return ans . 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
25
26
27 class Solution {
public :
string reorganizeString ( string s ) {
vector < int > cnt ( 26 );
for ( char & c : s ) ++ cnt [ c - 'a' ];
int mx = * max_element ( cnt . begin (), cnt . end ());
int n = s . size ();
if ( mx > ( n + 1 ) / 2 ) return "" ;
vector < vector < int >> m ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ]) m . push_back ({ cnt [ i ], i });
}
sort ( m . begin (), m . end ());
reverse ( m . begin (), m . end ());
string ans = s ;
int k = 0 ;
for ( auto & e : m ) {
int v = e [ 0 ], i = e [ 1 ];
while ( v -- ) {
ans [ k ] = 'a' + i ;
k += 2 ;
if ( k >= n ) k = 1 ;
}
}
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 func reorganizeString ( s string ) string {
cnt := make ([] int , 26 )
for _ , c := range s {
t := c - 'a'
cnt [ t ] ++
}
mx := slices . Max ( cnt )
n := len ( s )
if mx > ( n + 1 ) / 2 {
return ""
}
m := [][] int {}
for i , v := range cnt {
if v > 0 {
m = append ( m , [] int { v , i })
}
}
sort . Slice ( m , func ( i , j int ) bool {
return m [ i ][ 0 ] > m [ j ][ 0 ]
})
ans := make ([] byte , n )
k := 0
for _ , e := range m {
v , i := e [ 0 ], e [ 1 ]
for v > 0 {
ans [ k ] = byte ( 'a' + i )
k += 2
if k >= n {
k = 1
}
v --
}
}
return string ( 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
42
43
44
45
46
47
48 use std :: collections ::{ BinaryHeap , HashMap , VecDeque };
impl Solution {
#[allow(dead_code)]
pub fn reorganize_string ( s : String ) -> String {
let mut map = HashMap :: new ();
let mut pq = BinaryHeap :: new ();
let mut ret = String :: new ();
let mut queue = VecDeque :: new ();
let n = s . len ();
// Initialize the HashMap
for c in s . chars () {
map . entry ( c )
. and_modify ( | e | {
* e += 1 ;
})
. or_insert ( 1 );
}
// Initialize the binary heap
for ( k , v ) in map . iter () {
if 2 * * v - 1 > n {
return "" . to_string ();
} else {
pq . push (( * v , * k ));
}
}
while ! pq . is_empty () {
let ( v , k ) = pq . pop (). unwrap ();
ret . push ( k );
queue . push_back (( v - 1 , k ));
if queue . len () == 2 {
let ( v , k ) = queue . pop_front (). unwrap ();
if v != 0 {
pq . push (( v , k ));
}
}
}
if ret . len () == n {
ret
} else {
"" . to_string ()
}
}
}
Solution 2
Python3 Java C++ Go
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 :
return self . rearrangeString ( s , 2 )
def rearrangeString ( self , s : str , k : int ) -> str :
h = [( - v , c ) for c , v in Counter ( s ) . items ()]
heapify ( h )
q = deque ()
ans = []
while h :
v , c = heappop ( h )
v *= - 1
ans . append ( c )
q . append (( v - 1 , c ))
if len ( q ) >= k :
w , c = q . popleft ()
if w :
heappush ( h , ( - w , c ))
return "" if len ( ans ) != len ( s ) else "" . join ( 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 class Solution {
public String reorganizeString ( String s ) {
return rearrangeString ( s , 2 );
}
public String rearrangeString ( String s , int k ) {
int n = s . length ();
int [] cnt = new int [ 26 ] ;
for ( char c : s . toCharArray ()) {
++ cnt [ c - 'a' ] ;
}
PriorityQueue < int []> pq = new PriorityQueue <> (( a , b ) -> b [ 0 ] - a [ 0 ] );
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > 0 ) {
pq . offer ( new int [] { cnt [ i ] , i });
}
}
Deque < int []> q = new ArrayDeque <> ();
StringBuilder ans = new StringBuilder ();
while ( ! pq . isEmpty ()) {
var p = pq . poll ();
int v = p [ 0 ] , c = p [ 1 ] ;
ans . append (( char ) ( 'a' + c ));
q . offer ( new int [] { v - 1 , c });
if ( q . size () >= k ) {
p = q . pollFirst ();
if ( p [ 0 ] > 0 ) {
pq . offer ( p );
}
}
}
return ans . length () == n ? ans . 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
25
26
27
28
29 class Solution {
public :
string reorganizeString ( string s ) {
return rearrangeString ( s , 2 );
}
string rearrangeString ( string s , int k ) {
unordered_map < char , int > cnt ;
for ( char c : s ) ++ cnt [ c ];
priority_queue < pair < int , char >> pq ;
for ( auto & [ c , v ] : cnt ) pq . push ({ v , c });
queue < pair < int , char >> q ;
string ans ;
while ( ! pq . empty ()) {
auto [ v , c ] = pq . top ();
pq . pop ();
ans += c ;
q . push ({ v - 1 , c });
if ( q . size () >= k ) {
auto p = q . front ();
q . pop ();
if ( p . first ) {
pq . push ( p );
}
}
}
return ans . size () == s . size () ? 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
42
43
44
45
46
47
48
49 func reorganizeString ( s string ) string {
return rearrangeString ( s , 2 )
}
func rearrangeString ( s string , k int ) string {
cnt := map [ byte ] int {}
for i := range s {
cnt [ s [ i ]] ++
}
pq := hp {}
for c , v := range cnt {
heap . Push ( & pq , pair { v , c })
}
ans := [] byte {}
q := [] pair {}
for len ( pq ) > 0 {
p := heap . Pop ( & pq ).( pair )
v , c := p . v , p . c
ans = append ( ans , c )
q = append ( q , pair { v - 1 , c })
if len ( q ) >= k {
p = q [ 0 ]
q = q [ 1 :]
if p . v > 0 {
heap . Push ( & pq , p )
}
}
}
if len ( ans ) == len ( s ) {
return string ( ans )
}
return ""
}
type pair struct {
v int
c byte
}
type hp [] pair
func ( h hp ) Len () int { return len ( h ) }
func ( h hp ) Less ( i , j int ) bool {
a , b := h [ i ], h [ j ]
return a . v > b . v
}
func ( h hp ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * hp ) Push ( v any ) { * h = append ( * h , v .( pair )) }
func ( h * hp ) Pop () any { a := * h ; v := a [ len ( a ) - 1 ]; * h = a [: len ( a ) - 1 ]; return v }
GitHub