দুটি সংখ্যা n এবং k দেওয়া আছে। দৈর্ঘ্য k এবং ডিস্ট্যান্স n 가진 লেক্সিকোগ্রাফিক্যালি স্মলেস্ট লোয়ারকেস স্ট্রিং খুঁজে বের করতে হবে। ডিস্ট্যান্স = প্রতিটি অক্ষরের অ্যালফাবেটিক পজিশনের যোগফল (a=1, b=2, ..., z=26)।
উদাহরণ: n = 15, k = 3 হলে আউটপুট "aam"। কারণ 1 + 1 + 13 = 15 এবং লেক্সিকোগ্রাফিক্যালি স্মলেস্ট।
সমাধানের পদ্ধতি
লালচী (greedy) পদ্ধতি: সবচেয়ে ডানদিক থেকে শুরু করে যতটা সম্ভব বড় অক্ষর (z=26) বসান, বাকিগুলো 'a' রাখুন।
distঅ্যারে আকারk, সব মান ১ দিয়ে শুরু করুন (সব 'a')।credit = n - k(বাকি ডিস্ট্যান্স বান্টন বাকি)।- ডানদিক থেকে বামদিক (
i = k-1থেকে ০) যান: - প্রতিটি পজিশনে
val = min(credit, 25)যোগ করুন (অधিকতম ২৫ যোগ করলে 'z' হয়)। credit -= val,i--।credit == 0হলে বন্ধ করুন।distঅ্যারেকে ক্যারেক্টারে কনভার্ট করুন:chr(d - 1 + ord('a'))।
পাইথন কোড
def solve(n, k):
dist = [1] * k # সব 'a' দিয়ে শুরু
credit = n - k # বাকি ডিস্ট্যান্স
i = k - 1 # ডানদিক থেকে শুরু
while credit > 0:
val = min(credit, 25) # সর্বোচ্চ ২৫ যোগ করা যায় (a->z)
dist[i] += val
credit -= val
i -= 1
# সংখ্যাকে ক্যারেক্টারে কনভার্ট করুন
return "".join(chr(d - 1 + ord("a")) for d in dist)
# টেস্ট
n = 15
k = 3
print(solve(n, k)) # আউটপুট: aamব্যাখ্যা
লেক্সিকোগ্রাফিক্যালি স্মলেস্ট মানে বামদিকের অক্ষরগুলো যতটা সম্ভব ছোট ('a') রাখতে হবে। তাই ডানদিক থেকে বড় অক্ষর বসানো হয়।
সময় জটিলতা
O(k) - লিনিয়ার। স্পেস O(k)।
