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

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

যেমন, ইনপুট হলে s = "pqpqrrr", তবে আউটপুট হবে 5 কারণ ['p','q','pq','r','rr'] এভাবে ভাগ করা যায়। ['p','q','p','q','r','rr'] ভাগ করলে ভ্যালিড নয় কারণ 'p' ও 'q' একাধিকবার আসছে।

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

res := [0]
dfs(s, path=set()) ফাংশন ডিফাইন করুন:
- যদি s খালি হয়, তবে res[0] = max(res[0], len(path)), রিটার্ন করুন।
- i = 1 থেকে len(s) পর্যন্ত:
  - x := s[:i]
  - যদি x not in path হয়, তবে dfs(s[i:], path | {x})
মেইন থেকে dfs(s) কল করুন।
res[0] রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(s):
    res = [0]
    def dfs(s, path=set()):
        if not s:
            res[0] = max(res[0], len(path))
            return
        for i in range(1, len(s)+1):
            x = s[:i]
            if x not in path:
                dfs(s[i:], path | {x})
    dfs(s)
    return res[0]

s = "pqpqrrr"
print(solve(s))

ইনপুট

"pqpqrrr"