Post

778 Reorganize String

Posted Updated
By Anurag
1 min read
778 Reorganize String

Reorganize String image

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:

1
2
3

**Input:** s = "aab"
**Output:** "aba"

Example 2:

1
2
3

**Input:** s = "aaab"
**Output:** ""

 

Constraints:

1
2

1 <= s.length <= 500
s 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


class Solution:
    import heapq as hq
    
    def reorganizeString(self, s: str) -> str:
        result = [None] * len(s)
        h = []
        map_str = {

        }
        for ch in s:
            if ch in map_str:
                map_str[ch] = map_str[ch] + 1
            else:
                map_str[ch] = 1

        for k,v in map_str.items():
            heappush(h, (-1 * v, k))
        i = 0
        l = 0
        for (v,k) in h:
            (i, v) = self.fill_first(i, -v, k, result)
            h[l] = (-v, k)
            l = l + 1
            if v != 0:
                break
        print(h, result)
        i = 0
        for (v,k) in h:
            if v != 0:
                (i, v) = self.fill_next(i, -v, k, result)
        if None in result:
            return ""
        return "".join(result)



    def fill_next(self, i : int, v : int, k : str ,result : List) -> (int, int):
        while(i < len(result) and v > 0):
            if result[i] == None and result[i-1] != k:
                result[i] = k
                v = v - 1
            i = i + 1
        return (i, v)

    def fill_first(self, i : int, v : int, k : str ,result : List) -> (int, int):
        while(i < len(result) and v > 0):
            result[i] = k
            v = v - 1
            i = i + 2
        return (i, v)
leetcode
python
This post is licensed under CC BY 4.0 by the author.