Skip to content

767. Reorganize String

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.

Example 1:

Input: s = “aab”
Output: “aba”

Example 2:

Input: s = “aaab”
Output: “”

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Solve

Recursion

python

I try no simulating the process of try and error. Where start from total array of character s. I put the char in a current curr array one by one, while maintain any two adjacent characters in curr are not the same.

A TLE solution

Time Submitted Status Runtime Memory Language
08/23/2023 21:38 Time Limit Exceeded N/A N/A python3 
class Solution:
    def helper(self, curr, remain):
        if len(remain) == 0:
            self.result = curr
            return True
        for i, c in enumerate(remain):
            if len(curr) > 0 and curr[-1] == c:
                continue
            if self.helper(curr+c, remain[:i] + remain[i+1:]):
                return True
        return False


    def reorganizeString(self, s: str) -> str:
        self.result = ""
        self.helper("", s)
        return self.result

Greedy

python

When analyzing the result more, I trying to chose the best way to put character c form remain character of s into curr array.

So I come up with a greedy way to choose each element with this rule:

  • Sort all element by total count
  • Because all two adjacent element isn’t the same. We start with highest total count element x, put it all into curr array
  • The next loop, we push all other number one by one (from highest total count to lowest), separating all already pushed x.
  • If we success separating all x element, any remain character can be freely push into the array from by define.

I try some type of way to allocating memory, but it not that much affect the time complexity.

Time Submitted Status Runtime Memory Language
08/23/2023 21:57 Accepted 42 ms 16.2 MB python3
08/23/2023 21:55 Accepted 49 ms 16.2 MB python3
08/23/2023 21:49 Accepted 37 ms 16.4 MB python3 
class Solution:
    def reorganizeString(self, s: str) -> str:
        count = [0]*27
        for i in s:
            count[ord(i) - ord("a")] += 1

        keys = list(range(27))

        def sortKey(x):
            return -count[x]
        keys.sort(key = sortKey)

        atleast = 0
        res = ""
        for i, nc in enumerate(keys):
            c = chr(nc + ord("a"))
            if i == 0:
                res = c* count[nc]
                atleast = count[nc]
                continue
            for j in range(count[nc]):
                if atleast == 0:
                    atleast = len(res)
                atleast = atleast -1
                res = res[:atleast] + c + res[atleast:]
        if len(res) > 1 and res[0] == res[1]:
            return ""
        return res

JavaScript implementation

javascript

Normally, I won’t use JavaScript in any calculation, algorithm and mostly to interact with html dom, html element, handle web data, JSON, .... So this is quite a new experience

  • Array in JavaScript is similar to python, which is just a holder to any sequence of element (with no type enforce)
  • We can pushing element into array by using Array.splice
  • The equivalence JavaScript chr, ord function is String.fromCodePoint() and String.charCodeAt(0)
  • You can’t forEach on string.
  • We have Array.sort() which accept key function as two element as input. (python in the other hand only take one element)
Time Submitted Status Runtime Memory Language
08/23/2023 23:40 Accepted 57 ms 43.4 MB javascript 
/**

 * @param {string} s
 * @return {string}
 */
var reorganizeString = function(s) {
    const ordA = 'a'.charCodeAt(0);

    let count = Array(27)
    let keys = Array(27)

    for (let i = 0; i < 27; i++) {
        count[i] = 0
        keys[i] = i
    }

    Array.from(s).forEach ( (i) => {
        count[i.charCodeAt(0) - ordA] += 1
    })

    keys.sort( (a,b) => {
        return count[b]-count[a]
    }) 

    let result = Array(0)
    let currindex = 0
    for (let i = 0; i < 27; i ++) {
        c = String.fromCodePoint(keys[i] + ordA)
        if (i == 0) {
            result = Array(count[keys[0]])
            result.fill(c)
            currindex = count[keys[0]]
            continue
        }
        for (let j = 0; j < count[keys[i]]; j ++) {
            currindex -= 1
            if (currindex == 0)
                currindex = result.length
            result.splice(currindex, 0, c);
        }
    }
    if (result.length >= 2) 
        if (result[0] == result[1]) {
        return ""
    } 
    return result.join('')
};
Last update : October 13, 2023
Created : August 23, 2023