পাইথনে দেওয়া কনস্ট্রেইন্ট অনুযায়ী স্ট্রিং A থেকে স্ট্রিং B গঠন করা সম্ভব কিনা তা যাচাই করা

মান লিজিয়ে আমাদের দুটি স্ট্রিং s এবং t, এবং দুটি মান p এবং q আছে। আমাদের যাচাই করতে হবে s-থেকে t গঠন করা সম্ভব কিনা এমনভাবে যে s-কে p সংখ্যক ক্যারেক্টারের গ্রুপে ভাগ করা হবে শেষ গ্রুপটি p-এর চেয়ে ছোট বা সমান হতে পারে, এবং প্রতিটি গ্রুপ থেকে সর্বোচ্চ q সংখ্যক ক্যারেক্টার নেওয়া যাবে, এছাড়া t-এ ক্যারেক্টারগুলোর ক্রম s-এর মতোই থাকতে হবে।

যেমন, ইনপুট যদি s = "mnonnopeqrst", t = "moprst", p = 5, q = 2 হয়, তবে আউটপুট হবে True কারণ আমরা ভাগ করতে পারি: "mnonn", "opeqr", "st"। এখন "mnonn" এবং "opeqr"- থেকে ২ ক্যারেক্টার দিয়ে "mo" এবং "pr" নিলে এবং "st" যেহেতু ইতিমধ্যে আছে তাই এগুলো কনক্যাটেনেট (concatenate) করলে t পাওয়া যায়।

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

temp := সব কী-র জন্য খালি লিস্ট ধারণকারী একটি খালি ম্যাপ
l := s-এর দৈর্ঘ্যের সমান সাইজের একটি লিস্ট ০ দিয়ে ভরা
i ০ থেকে s-এর সাইজ পর্যন্ত, করুন:
- i-কে temp['a']-এর শেষে ইনসার্ট করুন
low := 0
i ০ থেকে t-এর সাইজ - ১ পর্যন্ত, করুন:
- indices := temp['a']
- it := indices-এ low ইনসার্ট করার ইনডেক্স যাতে সর্টেড অর্ডার মেইনটেইন হয়
- যদি it indices-এর সাইজ - ১ সমান হয়, তবে:
  - False রিটার্ন করুন
- count := indices[it] / p-এর ভাগফল
- l[count] := l[count] + 1
- যদি l[count] >= q হয়, তবে:
  - count := count + 1
  - low := count * p
- অন্যথায়:
  - low := indices[it] + 1
True রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

from bisect import bisect_left
from collections import defaultdict

def solve(s, t, b, m):
    temp = defaultdict(list)
    l = [0] * len(s)
    for i in range(len(s)):
        temp['a'].append(i)
    low = 0
    for i in range(len(t)):
        indices = temp['a']
        it = bisect_left(indices, low)
        if it == len(indices):
            return False
        count = indices[it] // b
        l[count] = l[count] + 1
        if l[count] >= m:
            count += 1
            low = count * b
        else:
            low = indices[it] + 1
    return True

s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print(solve(s, t, p, q))

ইনপুট

"mnonnopeqrst", "moprst", 5, 2

আউটপুট

True