Leetcode # 767. Reorganize String

Problem

https://leetcode.com/problems/reorganize-string

n := len(s)
k := len(set(s))

Solution

Time Complexity: O(n + k * log(k))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def reorganizeString(self, s: str) -> str:
    counter = Counter(s)
    chars = [k for k, c in counter.most_common() for _ in range(c)]
    i = j = 0
    n = len(s)
    result = [None] * n
    while i < n:
      result[i] = chars[j]
      i += 2 if j + 1 < n and chars[j + 1] == chars[j] else 1
      j += 1
    if j + 1 < n and chars[j] == result[0]: return ""
    i = 1
    while i < n:
      if result[i]:
        i += 1
        continue
      if i + 1 < n and result[i + 1] == chars[j]:
        return ""
      result[i] = chars[j]
      i += 1
      j += 1
    return "".join(result)

Last Updated on 2023/08/23 by A1go