পাইথনে অনন্য সাবস্ট্রিংগুলির সর্বাধিক সংখ্যায় একটি স্ট্রিংকে বিভক্ত করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের সর্বাধিক সংখ্যক অনন্য সাবস্ট্রিং খুঁজে বের করতে হবে যে প্রদত্ত স্ট্রিংটিকে বিভক্ত করা যেতে পারে। আমরা স্ট্রিং s কে অ-খালি সাবস্ট্রিংগুলির তালিকায় বিভক্ত করতে পারি যেমন সাবস্ট্রিংগুলির সংমিশ্রণ মূল স্ট্রিং গঠন করে। কিন্তু আমাদের অবশ্যই সাবস্ট্রিংগুলিকে এমনভাবে বিভক্ত করতে হবে যাতে সবগুলি একই হয়৷

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

res :=শুধুমাত্র একটি উপাদান 0 সহ একটি তালিকা
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি s, পাথ নেবে যা একটি নতুন খালি সেট
যদি s খালি হয়, তাহলে
- res[0] :=res এর সর্বাধিক [0] এবং পথের আকার
- প্রত্যাবর্তন
1 থেকে s আকারের রেঞ্জের জন্য,
- x :=s[সূচী ০ থেকে i-1]
- যদি x পাথে না থাকে, তাহলে
  - dfs(s এর সাবস্ট্রিং [index i থেকে শেষ পর্যন্ত], পাথ U {x})
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
dfs(s)
রিটার্ন রিটার্ন[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"