পাইথনে এক অদলবদল সহ লেক্সিকোগ্রাফিকভাবে সবচেয়ে ছোট স্ট্রিং খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের অভিধানগতভাবে সবচেয়ে ছোট স্ট্রিংটি খুঁজে বের করতে হবে যেটি তৈরি করা যেতে পারে যদি আমরা প্রদত্ত স্ট্রিং s-এর দুটি অক্ষরের মধ্যে সর্বাধিক একটি অদলবদল করতে পারি।

সুতরাং, ইনপুট যদি "zyzx" এর মত হয়, তাহলে আউটপুট হবে "xyzz"

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

• temp :=s আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
• m:=s - 1 এর আকার
• s -1 থেকে -1 রেঞ্জের আকারের i জন্য, 1 দ্বারা হ্রাস করুন, করুন
  • যদি s[i]
  • m :=i
• temp[i] :=m
• 0 থেকে s আকারের রেঞ্জের জন্য,
  করুন
  • a :=temp[i]
  • যদি s[a] s[i] এর মত না হয়, তাহলে
    • s এর সাবস্ট্রিং [সূচী 0 থেকে i পর্যন্ত] কনক্যাটেনেট s[a] s এর সাবস্ট্রিং [index i+1 থেকে a] concatenate s[i] s-এর সাবস্ট্রিং [index a+1 থেকে শেষ পর্যন্ত] li>

উদাহরণ

class Solution:
   def solve(self, s):
      temp = [0]*len(s)
      m=len(s)-1
      for i in range(len(s)-1, -1, -1):
         if s[i]<s[m]: m=i
            temp[i] = m
      for i in range(len(s)):
         a = temp[i]
         if s[a] != s[i]:
            return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
      return s
ob = Solution()
print(ob.solve("zyzx"))

ইনপুট

zyzx

আউটপুট

xyzz