Cho một chuỗi không rỗng str và một số nguyên k, hãy sắp xếp lại chuỗi sao cho các ký tự giống nhau cách nhau ít nhất k.
Tất cả các chuỗi đầu vào được viết bằng chữ thường. Nếu không thể sắp xếp lại chuỗi, hãy trả về một chuỗi trống "".
Ví dụ 1:
str = “tutorialspoint”, k = 3 Answer: “tiotiotalnprsu”
Các ký tự giống nhau cách nhau ít nhất 3 ký tự.
str = "aabbcc", k = 3 Answer: "abcabc" The same characters are at least 3 character distance apart.
Ví dụ 2
str = "aaabc", k = 3 Answer: "" It is not possible to rearrange the string.
Ví dụ 3:
str = "aaadbbcc", k = 2 Answer: "abacabcd" Another possible answer is: "abcabcda" The same characters are at least 2 character distance apart.
Ví dụ
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 ("It is not possible to rearrange the string.")
return
string[p + d*k] = x.c
return toString(string)
string = "tutorialspoint"
print (rearrange(toList(string), 3) )
Kết quả
tiotiotalnprsu