পাইথনে একটি স্ট্রিংয়ে অন্য স্ট্রিংয়ের সব ক্যারেক্টার ধারণকারী ন্যূনতম উইন্ডো খুঁজুন

সমস্যা বিবরণ

দুটি স্ট্রিং s1 এবং s2 দেওয়া আছে। s1-এ সবচেয়ে ছোট সাবস্ট্রিং খুঁজতে হবে যাতে s2-এর সব ক্যারেক্টার অন্তর্ভুক্ত থাকে (ফ্রিকোয়েন্সি বিবেচনায়)।

উদাহরণস্বরূপ, s1="I am a student", s2="mdn" হলে আউটপুট "m a studen"।

সমাধানের ধাপসমূহ

1. N = 256 (ASCII রেঞ্জ)।
2. hash_pat এবং hash_str ফ্রিকোয়েন্সি অ্যারে বানান।
3. s2-এর ক্যারেক্টার ফ্রিকোয়েন্সি hash_pat-এ স্টোর করুন।
4. স্লাইডিং উইন্ডো টেকনিক দিয়ে s1 স্ক্যান করুন:
   • start, start_index, min_len ট্র্যাক করুন।
   • count ভেরিয়েবল দিয়ে মিলে যাওয়া ক্যারেক্টার সংখ্যা গুনুন।
   • যদি count == len(s2) হয়, উইন্ডো ছোট করার চেষ্টা করুন।
   • ন্যূনতম উইন্ডো আপডেট করুন।
5. শেষে s1[start_index : start_index + min_len] রিটার্ন করুন।

পাইথন কোড উদাহরণ

N = 256

def get_pattern(main_str, pattern):
    str_len = len(main_str)
    patt_len = len(pattern)
    if str_len < patt_len:
        return None
    hash_pat = [0] * N
    hash_str = [0] * N
    for i in range(patt_len):
        hash_pat[ord(pattern[i])] += 1
    start = 0
    start_index = -1
    min_len = float('inf')
    count = 0
    for j in range(str_len):
        hash_str[ord(main_str[j])] += 1
        if hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]:
            count += 1
        if count == patt_len:
            while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
                if hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]:
                    hash_str[ord(main_str[start])] -= 1
                start += 1
            len_window = j - start + 1
            if min_len > len_window:
                min_len = len_window
                start_index = start
    if start_index == -1:
        return None
    return main_str[start_index : start_index + min_len]

main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))  # আউটপুট: m a studen

ইনপুট

"I am a student", "mdn"

আউটপুট

m a studen