767. Reorganize String - Explanation

Description

You are given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

You can return any possible rearrangement of s or return "" if not posssible.

Example 1:

Input: s = "axyy"

Output: "xyay"

Example 2:

Input: s = "abbccdd"

Output: "abcdbcd"

Example 3:

Input: s = "ccccd"

Output: ""

Constraints:

1 <= s.length <= 500.
s is made up of lowercase English characters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Frequency Count

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1

        max_freq = max(freq)
        if max_freq > (len(s) + 1) // 2:
            return ""

        res = []
        while len(res) < len(s):
            maxIdx = freq.index(max(freq))
            char = chr(maxIdx + ord('a'))
            res.append(char)
            freq[maxIdx] -= 1
            if freq[maxIdx] == 0:
                continue

            tmp = freq[maxIdx]
            freq[maxIdx] = float("-inf")
            nextMaxIdx = freq.index(max(freq))
            char = chr(nextMaxIdx + ord('a'))
            res.append(char)
            freq[maxIdx] = tmp
            freq[nextMaxIdx] -= 1

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.

2. Frequency Count (Max-Heap)

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)
        maxHeap = [[-cnt, char] for char, cnt in count.items()]
        heapq.heapify(maxHeap)

        prev = None
        res = ""
        while maxHeap or prev:
            if prev and not maxHeap:
                return ""

            cnt, char = heapq.heappop(maxHeap)
            res += char
            cnt += 1

            if prev:
                heapq.heappush(maxHeap, prev)
                prev = None

            if cnt != 0:
                prev = [cnt, char]

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.

3. Frequency Count (Greedy)

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1

        max_idx = freq.index(max(freq))
        max_freq = freq[max_idx]
        if max_freq > (len(s) + 1) // 2:
            return ""

        res = [''] * len(s)
        idx = 0
        max_char = chr(max_idx + ord('a'))

        while freq[max_idx] > 0:
            res[idx] = max_char
            idx += 2
            freq[max_idx] -= 1

        for i in range(26):
            while freq[i] > 0:
                if idx >= len(s):
                    idx = 1
                res[idx] = chr(i + ord('a'))
                idx += 2
                freq[i] -= 1

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.