পাইথনে নন-ওভারল্যাপিং সাবস্ট্রিংয়ের সর্বোচ্চ সংখ্যা বের করার প্রোগ্রাম

মনে করুন s নামক একটি স্ট্রিং আছে যাতে শুধু লোয়ারকেস লেটার। আমাদের s-এর নন-এম্পটি সাবস্ট্রিংয়ের সর্বোচ্চ সংখ্যা বের করতে হবে যারা নিচের শর্ত মেনে চলে:

• সাবস্ট্রিংগুলো নন-ওভারল্যাপিং হবে।

• যদি একটি সাবস্ট্রিং নির্দিষ্ট ক্যারেক্টার ch ধারণ করে, তবে সেটাকে ch-এর সকল অকারেন্সও ধারণ করতে হবে।

এই দুটি শর্ত পূরণ করা সাবস্ট্রিংয়ের সর্বোচ্চ সংখ্যা বের করতে হবে। একাধিক সমাধান হলে সেটা রিটার্ন করুন যেটার মোট দৈর্ঘ্য ন্যূনতম।

যেমন, ইনপুট s = "pqstpqqprrr" হলে, আউটপুট হবে ["s","t","rrr"] কারণ শর্ত পূরণকারী সব সাবস্ট্রিং: ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]।

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

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

• right := s-এ থাকা প্রতিটি ক্যারেক্টার ch-এর ডানপাশের ইনডেক্স পজিশন সর্ট করা লিস্ট

• left := right-এ থাকা প্রতিটি i-এর জন্য s[i]-এর বামপাশের ইনডেক্স লিস্ট

• has := খালি লিস্ট, gen := খালি লিস্ট

• i = 0 থেকে right-এর সাইজ - ১ পর্যন্ত

  • gen-এ s[right[i]]-এর ক্যারেক্টার সেট অ্যাপেন্ড করুন

  • has-এ s[left[i]+1 : right[i]] সাবস্ট্রিংয়ের ক্যারেক্টার সেট থেকে gen-এর শেষ আইটেম বাদ দিয়ে অ্যাপেন্ড করুন

  • j = has-এর সাইজ - ২ থেকে ০ পর্যন্ত (কমাতে ১)

    • যদি (has[-1] & gen[j]) এবং (has[j] & gen[-1]) দুটোই নন-জিরো হয়, তবে

      • gen[-1] := gen[-1] | gen[j]

      • has[-1] := (has[-1] | has[j]) - gen[-1]

      • has[j], gen[j] ডিলিট করুন

• res := খালি লিস্ট, p_right := -1

• ind = 0 থেকে has-এর সাইজ - ১ পর্যন্ত

  • l := left-এ থাকা i যারা s[i] gen[ind]-এ আছে, তাদের মিনিমাম

  • r := right-এ থাকা i যারা s[i] gen[ind]-এ আছে, তাদের ম্যাক্সিমাম

  • যদি p_right < l হয়, তবে

    • s[l : r+1] সাবস্ট্রিং res-এ অ্যাপেন্ড করুন

    • p_right := r

• res রিটার্ন করুন

উদাহরণ

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

def solve(s):    right = sorted([s.rindex(ch) for ch in set(s)])    left = [s.index(s[i]) for i in right]      has, gen = [], []    for i in range(len(right)):       gen.append(set(s[right[i]]))       has.append(set(s[left[i] + 1:right[i]]) - gen[-1])    for j in range(len(has) - 2, -1, -1):       if (has[-1] & gen[j]) and (has[j] & gen[-1]):          gen[-1] = gen[-1] | gen[j]          has[-1] = (has[-1] | has[j]) - gen[-1]          del has[j], gen[j]    res, p_right = [], -1    for ind in range(len(has)):       l = min([i for i in left if s[i] in gen[ind]])       r = max([i for i in right if s[i] in gen[ind]]) if p_right < l: res.append(s[l : r + 1]) p_right = r return res s = "pqstpqqprrr" print(solve(s))

ইনপুট

"pqstpqqprrr"

আউটপুট

['s', 't', 'rrr']