Greedy
Hash Table
String
Counting
Sorting
Heap (Priority Queue)
Description
Given a string s
and an integer k
, rearrange s
such that the same characters are at least distance k
from each other. If it is not possible to rearrange the string, return an empty string ""
.
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.
Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.
Constraints:
1 <= s.length <= 3 * 105
s
consists of only lowercase English letters.
0 <= k <= s.length
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
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 class Solution {
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 class Solution {
public :
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 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