পাইথনে প্রিফিক্স অ্যারে অনুযায়ী লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট স্ট্রিং নির্ণয়

একটি অ্যারে A দেওয়া আছে যেখানে A[i] বোঝায় দৈর্ঘ্য (i+1)-এর প্রিফিক্স-এ কতগুলো স্বতন্ত্র ক্যারেক্টার আছে। এই শর্ত পূরণ করে লেক্সিকোগ্রাফিক্যালি (lexicographically) সবচেয়ে ছোট স্ট্রিং বের করতে হবে। সব ক্যারেক্টার ছোট হাতের ইংরেজি অক্ষর (a-z)।

উদাহরণ

ইনপুট: A = [1, 1, 2, 3, 4]

আউটপুট: "aabcd"

ব্যাখ্যা: prefix[0]="a" (১টি یونিক), prefix[1]="aa" (১টি ইউনিক), prefix[2]="aab" (২টি ইউনিক), prefix[3]="aabc" (৩টি ইউনিক), prefix[4]="aabcd" (৪টি ইউনিক)।

সমাধানের পদ্ধতি

1. প্রথম ক্যারেক্টর অবশ্যই 'a' হবে (A[0] == 1 হলে)।
2. পরবর্তী ইনডেক্সগুলোতে: difference = A[i] - A[i-1]
3. যদি difference > 1 বা < 0 বা A[i] > 26 হয়, তবে অসম্ভব → -1।
4. যদি difference == 0 হয়, তবে 'a' যোগ করা হয় (নতুন ক্যারেক্টার না যোগ করে)।
5. যদি difference == 1 হয়, তবে পরবর্তী নতুন ক্যারেক্টার (b, c, d...) যোগ করা হয়।

পাইথন কোড

def get_smallest_string(A):
    n = len(A)
    character = 'a'
    string = ""
    
    if n < 1 or A[0] != 1:
        return -1
    
    string += character
    character = chr(ord(character) + 1)
    
    for i in range(1, n):
        difference = A[i] - A[i - 1]
        if difference > 1 or difference < 0 or A[i] > 26:
            return -1
        elif difference == 0:
            string += 'a'
        else:
            string += character
            character = chr(ord(character) + 1)
    
    return string

A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))

ইনপুট

[1, 1, 2, 3, 4]

আউটপুট

aabcd