পাইথনে দিয়ে k সংখ্যক یونিক ক্যারেক্টার সম্বলিত দীর্ঘতম সাবস্ট্রিং খুঁজে বের করা

একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-এ ঠিক k সংখ্যক ইউনিক (unique) ক্যারেক্টার সম্বলিত দীর্ঘতম সাবস্ট্রিং (substring) খুঁজে বের করতে হবে। একাধিক হলে যেকোনো একটি ফেরত দিন।

উদাহরণ

ইনপুট: s = "ppqprqtqtqt", k = 3

আউটপুট: "rqtqtqt" (দৈর্ঘ্য ৭)

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

1. স্লাইডিং উইন্ডো (Sliding Window) টেকনিক ব্যবহার করা হয়।
2. দুটি পয়েন্টার `start` এবং `end` দিয়ে উইন্ডো মেইনটেইন করা হয়।
3. ক্যারেক্টার ফ্রিকোয়েন্সি আরে দিয়ে ইউনিক ক্যারেক্টার সংখ্যা ট্র্যাক করা হয়।
4. `end` বাড়িয়ে উইন্ডো বড় করা হয়, ইউনিক ক্যারেক্টার > k হলে `start` বাড়িয়ে কমানো হয়।
5. সর্বোচ্চ দৈর্ঘ্যের উইন্ডো রেকর্ড করা হয়।

পাইথন কোড

N = 26

def is_ok(count, k):
    val = 0
    for i in range(N):
        if count[i] > 0:
            val += 1
    return k >= val

def k_unique_chars(s, k):
    unique = 0
    size = len(s)
    count = [0] * N
    
    for i in range(size):
        if count[ord(s[i]) - ord('a')] == 0:
            unique += 1
        count[ord(s[i]) - ord('a')] += 1
    
    if unique < k:
        return "Not sufficient characters"
    
    start = 0
    end = 0
    window_length = 1
    window_start = 0
    count = [0] * N
    count[ord(s[0]) - ord('a')] += 1
    
    for i in range(1, size):
        count[ord(s[i]) - ord('a')] += 1
        end += 1
        
        while not is_ok(count, k):
            count[ord(s[start]) - ord('a')] -= 1
            start += 1
        
        if end - start + 1 > window_length:
            window_length = end - start + 1
            window_start = start
    
    return s[window_start:window_start + window_length]

s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))

ইনপুট

"ppqprqtqtqt", 3

আউটপুট

rqtqtqt