难度: Hard
Submission
运行时间: 58 ms
内存: 0.0 MB
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
temp = Counter(s)
temp = [[i,j] for i,j in temp.items()]
temp.sort(key = lambda x: -x[1])
n = len(s)
count = len([i for i in temp if i[1] == temp[0][1]])
if (temp[0][1] - 1) * k + 1 + count - 1> n:
return ""
ans = ['_'] * n
j = 0
for i in temp:
# print(ans)
while i[1] > 0 and ans[j] != '_':
j = (j + 1) % n
while i[1] > 0:
# print(ans)
# print(j, i)
ans[j] = i[0]
i[1] -= 1
if i[1] > 0:
j += k
if j >= n:
j = 0
while i[1] > 0 and ans[j] != '_':
j = (j + 1) % n
return ''.join(ans)
Explain
这个题解的思路是先统计每个字符出现的频率，然后将字符按频率从大到小排序。接下来检查出现频率最高的字符是否会导致无法构造有效的重排后字符串，如果无法构造则直接返回空字符串。如果可以构造，则创建一个长度为n的数组ans，初始化为'_'。然后从频率最高的字符开始，每次将字符放到ans中当前位置，并将当前位置向后移动k个位置。如果到达末尾，则回到开头继续。每放置一个字符，就将该字符的剩余数量减1，直到所有字符都放置完毕。最后将ans数组转换为字符串返回。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
# 统计每个字符出现的频率
temp = Counter(s)
# 将字符频率对转换为列表并按频率从大到小排序
temp = [[i,j] for i,j in temp.items()]
temp.sort(key = lambda x: -x[1])
n = len(s)
# 检查出现频率最高的字符是否会导致无法构造有效的重排后字符串
count = len([i for i in temp if i[1] == temp[0][1]])
if (temp[0][1] - 1) * k + 1 + count - 1> n:
return ""
# 创建长度为n的ans数组，初始化为'_'
ans = ['_'] * n
j = 0
# 从频率最高的字符开始放置
for i in temp:
# 如果当前位置已有字符，则向后移动一位
while i[1] > 0 and ans[j] != '_':
j = (j + 1) % n
# 将字符放置到ans中，每次放置后将剩余数量减1，并将位置向后移动k个位置
while i[1] > 0:
ans[j] = i[0]
i[1] -= 1
if i[1] > 0:
j += k
if j >= n:
j = 0
# 如果新位置已有字符，则继续向后移动直到找到空位置
while i[1] > 0 and ans[j] != '_':
j = (j + 1) % n
# 将ans数组转换为字符串返回
return ''.join(ans)
Explore
在将字符根据频率从大到小排序之后，我从频率最高的字符开始进行放置。具体实施时，我设定初始位置（例如数组的起始位置），并在每次放置一个字符后，将当前位置向后移动k个位置。这样做可以保证每次放入的字符之间都至少有k-1个其他字符或者为空，从而满足题设的要求。如果当前位置超过了数组的长度，我会将其回绕到数组的开头，继续寻找空位进行放置，确保间隔k的规则得到遵守。
在我的实现中，如果我按照间隔k移动到一个新的位置，并发现该位置已经被其他字符占用，我会从当前位置开始，继续向后搜索直到找到一个空的位置。这种线性探测的方法虽然可能增加了额外的计算，但可以保证即使在位置已满的情况下也能找到合适的位置来放置当前字符，并且保持每两个相同字符之间的最小间隔为k。
环状处理确实有可能导致无限循环，特别是当没有足够的空间按照间隔k放置字符时。为了避免这种情况，我在开始放置字符之前进行了一个预检查，即检测频率最高的字符数量是否会导致放置失败。此外，实际放置过程中，每放置一个字符，我都会减少该字符的剩余数量，并仅当字符还有剩余时才继续寻找新的放置位置。一旦所有字符都放置完毕，循环即会结束，从而避免了无限循环。
这个表达式用于确保即使频率最高的字符也可以在字符串中按照间隔k被安排。这里，`(temp[0][1] - 1) * k + 1` 表示如果要放置频率最高的字符，至少需要的位置数。`temp[0][1] - 1` 代表除了第一个字符外的其他字符，每个字符后都需要至少k个间隔，`+ 1` 是放置第一个字符所需的位置。`+ count - 1` 考虑了如果有多个字符频率与最高频率相同，它们可能需要额外的位置。如果这个总需求超过了字符串长度n，则说明无法成功构造满足条件的重排字符串，因此返回空字符串。