একটি নন-এম্পটি স্ট্রিং str এবং একটি ইন্টিজার k দেওয়া আছে, স্ট্রিংটি পুনর্বিন্যাস করুন যাতে একই ক্যারেক্টারগুলো একে অপরের থেকে কমপক্ষে দূরত্ব k থাকে।
সকল ইনপুট স্ট্রিং লোয়ারকেস লেটারে দেওয়া থাকে। যদি স্ট্রিংটি পুনর্বিন্যাস করা সম্ভব না হয়, তবে খালি স্ট্রিং "" রিটার্ন করুন।
উদাহরণ ১:
str = "tutorialspoint", k = 3 Answer: "tiotiotalnprsu"
একই ক্যারেক্টারগুলো কমপক্ষে ৩ ক্যারেক্টার দূরত্বে রয়েছে।
str = "aabbcc", k = 3 Answer: "abcabc" একই ক্যারেক্টারগুলো কমপক্ষে ৩ ক্যারেক্টার দূরত্বে রয়েছে।
উদাহরণ ২
str = "aaabc", k = 3 Answer: "" স্ট্রিংটি পুনর্বিন্যাস করা সম্ভব নয়।
উদাহরণ ৩:
str = "aaadbbcc", k = 2 Answer: "abacabcd" আরেকটি সম্ভাব্য উত্তর: "abcabcda" একই ক্যারেক্টারগুলো কমপক্ষে ২ ক্যারেক্টার দূরত্বে রয়েছে।
প্রোগ্রাম
MAX = 128
# একটি ক্যারেক্টার 'char' এবং এর ফ্রিকোয়েন্সি 'freq' সংরক্ষণের জন্য স্ট্রাকচার
# ইনপুট স্ট্রিং-এ
class charFreq(object):
def __init__(self, char, freq):
self.c = char
self.f = freq
# দুটি charFreq আইটেম স왪 করার ইউটিলিটি ফাংশন
def swap(x, y):
return y, x
# স্ট্রিংকে লিস্টে কনভার্ট করার ইউটিলিটি ফাংশন
def toList(string):
t = []
for x in string:
t.append(x)
return t
# লিস্টকে স্ট্রিংে কনভার্ট করার ইউটিলিটি ফাংশন
def toString(l):
return ''.join(l)
# freq[]-এ সংরক্ষিত হিপের নোড freq[i]-কে ম্যাক্সহিপিফাই করার ইউটিলিটি ফাংশন
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)
# freq[] অ্যারেকে ম্যাক্স হিপে কনভার্ট করার ইউটিলিটি ফাংশন
def buildHeap(freq, n):
i = (n - 1) // 2
while i >= 0:
maxHeapify(freq, i, n)
i -= 1
# ম্যাক্স হিপ থেকে ম্যাক্স আইটেম বা রুট রিমুভ করার ইউটিলিটি ফাংশন
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
# মূল ফাংশন যা ইনপুট স্ট্রিং 'str'-কে পুনর্বিন্যাস করে যাতে
# দুই সেম ক্যারেক্টার d দূরত্বে চলে যায়
def rearrange(string, d):
# ইনপুট স্ট্রিংর দৈর্ঘ্য বের করুন
n = len(string)
# স্ট্রিং-এ সব ক্যারেক্টার ও তাদের ফ্রিকোয়েন্সি সংরক্ষণের জন্য অ্যারে
freq = []
for x in range(MAX):
freq.append(charFreq(0, 0))
m = 0
# ইনপুট স্ট্রিং ট্রাভার্স করে সব ক্যারেক্টারের ফ্রিকোয়েন্সি freq[]-এ স্টোর করুন
for i in range(n):
x = ord(string[i])
# যদি এই ক্যারেক্টার প্রথমবার আসে, m ইনক্রিমেন্ট করুন
if freq[x].c == 0:
freq[x].c = chr(x)
m += 1
freq[x].f += 1
string[i] = '\0'
# সব ক্যারেক্টারের ম্যাক্স হিপ বানান
buildHeap(freq, MAX)
# এখন এক-এক করে ম্যাক্স হিপ থেকে সব ডISTINCT ক্যারেক্টার এক্সট্রাক্ট করুন
# এবং স্ট্রিং-এ d দূরত্ব কনস্ট্রেইন্ট সহ ফিরিয়ে দিন
for i in range(m):
x = extractMax(freq, MAX - i)
# স্ট্রিং-এ প্রথম উপলব্ধ পজিশন খুঁজুন
p = i
while string[p] != '\0':
p += 1
# x.c কে p, p+d, p+2d, .. p+(f-1)d পজিশনে ফিল করুন
for k in range(x.f):
# যদি ইনডেক্স সাইজের বাইরে চলে যায়, তবে স্ট্রিং পুনর্বিন্যাস করা যাবে না
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))
রেজাল্ট
tiotiotalnprsu
