পাইথন ব্যবহার করে দীর্ঘতম সুন্দর সাবস্ট্রিং খুঁজে পেতে প্রোগ্রাম

ধরুন আমরা একটি স্ট্রিং s আছে. আমাদের s এর দীর্ঘতম সুন্দর সাবস্ট্রিং খুঁজে বের করতে হবে। একটি স্ট্রিং s এর জন্য, এটিকে সুন্দর বলা হবে যখন, s-এ বর্ণমালার প্রতিটি অক্ষরের জন্য, এটি বড় হাতের এবং ছোট হাতের উভয় অক্ষরে প্রদর্শিত হবে। যদি এই ধরনের একাধিক সাবস্ট্রিং থাকে, তাহলে সবচেয়ে আগের সাবস্ট্রিংটি ফেরত দিন।

সুতরাং, যদি ইনপুটটি s ="ZbybBbz" এর মত হয়, তাহলে আউটপুট হবে "bBb" কারণ এতে ছোট হাতের এবং বড় হাতের B' রয়েছে।

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

cur_max:=-1
res:=ফাঁকা স্ট্রিং
0 থেকে s আকারের রেঞ্জের জন্য, করুন
- c :=s[i]
- উপরের :=একটি নতুন সেট
- low :=একটি নতুন সেট
- যদি c ছোট হাতের অক্ষরে হয়, তাহলে
  - নিচের মধ্যে c যোগ করুন
- যদি c বড় হাতের অক্ষরে থাকে, তাহলে
  - বড়ে c যোগ করুন কিন্তু আগে ছোট হাতের অক্ষরে রূপান্তর করুন
- j রেঞ্জ i+1 থেকে s এর আকারের জন্য, করুন
  - c :=s[j]
  - যদি c ছোট হাতের অক্ষরে হয়, তাহলে
    - নিচের মধ্যে c যোগ করুন
  - যদি c বড় হাতের অক্ষরে থাকে, তাহলে
    - বড়ে c যোগ করুন কিন্তু আগে ছোট হাতের অক্ষরে রূপান্তর করুন
  - যদি উপরেরটি নীচের সমান হয়, তাহলে
    - যদি j-i> cur_max, তাহলে
      - cur_max :=j-i
      - res :=s এর সাবস্ট্রিং [index i থেকে j+1]
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

def solve(s):
   cur_max= -1
   res=""
   for i in range(len(s)):
      c = s[i]
      upper = set()
      lower = set()
      if c.islower():
         lower.add(c)
      if c.isupper():
         upper.add(c.lower())
      for j in range(i+1,len(s)):
         c = s[j]
         if c.islower():
            lower.add(c)
         if c.isupper():
            upper.add(c.lower())
         if upper == lower:
            if j-i>cur_max:
               cur_max = j-i
               res = s[i:j+1]
   return res
s = "ZbybBbz"
print(solve(s))

ইনপুট

"ZbybBbz"

আউটপুট

bBb