What is the primary strategy to solve the 'Reorganize String' problem?

The primary strategy is a greedy approach where you prioritize placing the most frequent characters first, ensuring that no adjacent characters are the same.

How does the heap (priority queue) help in this problem?

The heap allows you to efficiently access the most frequent character available and manage its placement while maintaining the greedy approach.

What happens if the string cannot be rearranged to avoid adjacent characters being the same?

If the string cannot be rearranged due to character frequency constraints, the solution should return an empty string.

What is the complexity of the 'Reorganize String' solution?

The time complexity is dependent on heap operations, and the space complexity is O(n), where n is the length of the string.

Can this solution be optimized further for space or time?

Optimizations might be possible based on the specific constraints or properties of the input string, such as if it contains a small set of distinct characters.

#767

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

重构字符串

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。示例 1: 输入: s = "aab" 输出: "aba" 示例 2: 输入: s = "aaab" 输出: "" 提示: 1 s 只包含小写字母

哈希表字符串贪心排序堆（优先队列）

题目描述

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:

输入: s = "aab"
输出: "aba"

示例 2:

输入: s = "aaab"
输出: ""

提示:

1 <= s.length <= 500
s 只包含小写字母

lightbulb

解题思路

方法一：哈希表

利用哈希表 cnt 统计字符串 s 中每个字符出现的次数。

若最大的出现次数 mx 大于 (n + 1) / 2，说明一定会存在两个相同字符相邻，直接返回 ''。

否则，按字符出现频率从大到小遍历，依次间隔 1 个位置填充字符。若位置大于等于 n，则重置为 1 继续填充。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        mx = max(cnt.values())
        if mx > (n + 1) // 2:
            return ''
        i = 0
        ans = [None] * n
        for k, v in cnt.most_common():
            while v:
                ans[i] = k
                v -= 1
                i += 2
                if i >= n:
                    i = 1
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate effectively handle character frequencies and heap operations?
question_mark
Do they understand how to balance greedy choices with validation of the invariant (no adjacent characters)?
question_mark
Is the candidate able to identify edge cases where rearrangement is impossible?

warning

常见陷阱

外企场景

error
Failing to handle edge cases where no valid rearrangement is possible, such as a string with all identical characters.
error
Not correctly maintaining the heap, leading to inefficient access to the most frequent characters.
error
Misunderstanding the greedy nature of the approach, leading to incorrect placements of characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string is already rearranged correctly? How do we optimize this?
arrow_right_alt
Can we optimize space usage if the string only consists of a few distinct characters?
arrow_right_alt
How would the approach change if the problem allowed for non-adjacent characters being the same?

help

常见问题

外企场景

继续练习

#692 前K个高频单词 #621 任务调度器 #1054 距离相等的条形码