Python程序重新排列字符串，以使所有相同字符相距d
给定一个非空字符串str和一个整数k，请重新排列该字符串，以使相同字符之间的距离至少为k。
所有输入字符串均以小写字母给出。如果无法重新排列字符串，则返回一个空字符串“”。
范例1：
str = “nhooo”, k = 3 Answer: “tiotiotalnprsu”
相同的字符至少要相距3个字符。
str = "aabbcc", k = 3 Answer: "abcabc" The same characters are at least 3 character distance apart.
例子2
str = "aaabc", k = 3 Answer: "" 无法重新排列字符串。
范例3：
str = "aaadbbcc", k = 2 Answer: "abacabcd" Another possible answer is: "abcabcda" The same characters are at least 2 character distance apart.
示例
MAX = 128
# A structure to store a character 'char' and its frequency 'freq'
# in input string
class charFreq(object):
def __init__(self,char,freq):
self.c = char
self.f = freq
# A utility function to swap two charFreq items.
def swap(x, y):
return y, x
# A utility function
def toList(string):
t = []
for x in string:
t.append(x)
return t
# A utility function
def toString(l):
return ''.join(l)
# A utility function to maxheapify the node freq[i] of a heap stored in freq[]
def maxHeapify(freq, i, heap_size):
l = i*2 + 1
r = i*2 + 2
largest = i
if l < heap_size and freq[l].f > freq[i].f:
largest = l
if r < heap_size and freq[r].f > freq[largest].f:
largest = r
if largest != i:
freq[i], freq[largest] = swap(freq[i], freq[largest])
maxHeapify(freq, largest, heap_size)
# A utility function to convert the array freq[] to a max heap
def buildHeap(freq, n):
i = (n - 1)//2
while i >= 0:
maxHeapify(freq, i, n)
i-=1
# A utility function to remove the max item or root from max heap
def extractMax(freq, heap_size):
root = freq[0]
if heap_size > 1:
freq[0] = freq[heap_size-1]
maxHeapify(freq, 0, heap_size-1)
return root
# The main function that rearranges input string 'str' such that
# two same characters become d distance away
def rearrange(string, d):
# Find length of input string
n = len(string)
# Create an array to store all characters and their
# frequencies in str[]
freq = []
for x in range(MAX):
freq.append(charFreq(0,0))
m = 0
# Traverse the input string and store frequencies of all
# characters in freq[] array.
for i in range(n):
x = ord(string[i])
# If this character has occurred first time, increment m
if freq[x].c == 0:
freq[x].c = chr(x)
m+=1
freq[x].f+=1
string[i] = '\0'
# Build a max heap of all characters
buildHeap(freq, MAX)
# Now one by one extract all distinct characters from max heap
# and put them back in str[] with the d distance constraint
for i in range(m):
x = extractMax(freq, MAX-i)
# Find the first available position in str[]
p = i
while string[p] != '\0':
p+=1
# Fill x.c at p, p+d, p+2d, .. p+(f-1)d
for k in range(x.f):
# If the index goes beyond size, then string cannot
# be rearranged.
if p + d*k >= n:
print ("无法重新排列字符串。")
return
string[p + d*k] = x.c
return toString(string)
string = "nhooo"
print (rearrange(toList(string), 3) )结果
tiotiotalnprsu