k间隔距离重排字符串python

K间隔距离重排字符串是指给定一个字符串S和一个整数K，允许你将S中的字符按任意顺序排列，但相邻字符之间的最大距离必须是K。例如，如果你有字符串"S" = "ABCD" 和 K = 2，你可以将其重排成 "ACDB" 或者 "ADBC"，但不能是 "ABC" 因为"A"和"B"之间只有1个位置。

在Python中，解决这个问题的一种常见方法是利用滑动窗口策略，同时维护两个指针，一个从前往后移动（左指针），另一个从后往前移动（右指针）。然后按照K的距离移动右指针，并尝试找到满足条件的排列。可以先创建一个频率字典来记录每个字符及其出现次数，再根据这个字典和K的限制构建可能的排列组合。

以下是一个简单的示例代码：

from collections import Counter

def k_distance_string(S, K):
    freq = Counter(S)
    n = len(freq)
    
    # 使用双端队列保存需要保持连续的字符序列
    queue = [(freq[char], char) for char in freq]
    queue.sort(reverse=True)
    
    result = ''
    left, right = 0, min(n, K - 1)
    
    while left < right and right <= n:
        if queue[left][0] == queue[right][0]:  # 同样频率的字符，向后移动右指针
            result += queue[right][1]
            right += 1
        else:  # 异频字符，选择频率较大的添加到结果并更新左指针
            result += queue[left][1]
            left += 1
    
    return result if len(result) == n else None

# 测试
S = "ABCD"
K = 2
print(k_distance_string(S, K))  # 输出："ACDB" 或 "ADCB"