পাইথনে সমান সাবস্ট্রিং জোড়ার সংখ্যা খুঁজে বের করার প্রোগ্রাম

আমাদের দুটি স্ট্রিং দেওয়া আছে, দুটোই ছোট হাতের অক্ষরের বানানো। আমাদের কোয়াড্রুপল (p, q, r, s) এর সংখ্যা বের করতে হবে যা নিচের শর্তগুলো পূরণ করে:

0 ≤ p ≤ q ≤ প্রথম স্ট্রিংর দৈর্ঘ্য
0 ≤ r ≤ s ≤ দ্বিতীয় স্ট্রিংর দৈর্ঘ্য
প্রথম স্ট্রিংর p ইন্ডেক্স থেকে শুরু করে q ইন্ডেক্সে শেষ হওয়া সাবস্ট্রিংটি দ্বিতীয় স্ট্রিংর r ইন্ডেক্স থেকে শুরু করে s ইন্ডেক্সে শেষ হওয়া সাবস্ট্রিংটির সমান হতে হবে।
q - r-এর মান উপরের শর্তগুলো পূরণকারী সব কোয়াড্রুপলে ন্যূনতম হতে হবে।

আমাদের এমন কোয়াড্রুপলের সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট firstString = 'hgfn', secondString = 'gfrt' হলে আউটপুট হবে 2।

দুটি কোয়াড্রুপল (1, 1, 0, 0) এবং (2, 2, 1, 1) শর্তগুলো পূরণ করে এবং q - r-এর ন্যূনতম মান থাকে।

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

left := 26 আকারের লিস্ট, সব মান infinity
right := 26 আকারের লিস্ট, সব মান -1
res := 0
mi := infinity
firstString-এর প্রতিটি ইন্ডেক্স i এবং ক্যারেক্টার ch এর জন্য:
- left[ord(ch) - ord('a')] := min(left[ord(ch) - ord('a')], i)
secondString-এর প্রতিটি ইন্ডেক্স i এবং ক্যারেক্টার ch এর জন্য:
- right[ord(ch) - ord('a')] := max(right[ord(ch) - ord('a')], i)
i = 0 থেকে 25 পর্যন্ত লুপ চালান:
- যদি left[i] != -1 হয়, তবে:
  - mi := min(mi, left[i] - right[i])
i = 0 থেকে 25 পর্যন্ত লুপ চালান:
- যদি left[i] != infinity এবং right[i] != -1 হয়, তবে:
  - যদি left[i] - right[i] == mi হয়, তবে:
    - res := res + 1
res রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(firstString, secondString):
    left = [float('inf')] * 26
    right = [-1] * 26
    res = 0
    mi = float('inf')
    for i, ch in enumerate(firstString):
        left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
    for i, ch in enumerate(secondString):
        right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
    for i in range(26):
        if left[i] != -1:
            mi = min(mi, left[i] - right[i])
    for i in range(26):
        if left[i] != float('inf') and right[i] != -1:
            if left[i] - right[i] == mi:
                res += 1
    return res

print(solve('hgfn', 'gfrt'))

ইনপুট

'hgfn', 'gfrt'