export function reorganizeString(s: string): string {
  const charCounts: Record<string, number> = {}
  const length = s.length

  for (let i = 0; i < length; i++) {
    const key = s[i]

    if (!charCounts[key]) charCounts[key] = 0
    charCounts[key]++
  }

  const result = Array<string>(length)

  for (let i = 0; i < length; i++) {
    let placed = false

    for (const key in charCounts) {
      if (
        charCounts[key] > 0 &&
        (i === 0 || result[i - 1] !== key)
      ) {
        result[i] = key
        charCounts[key]--
        placed = true
        break
      }
    }

    if (!placed) {
      return ''
    }
  }

  return result.join('')
}