पायथन में एक स्वैप के साथ लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग ढूंढनी है जो दी गई स्ट्रिंग s में दो वर्णों के बीच अधिकतम एक स्वैप करके बनाई जा सकती है।

उदाहरण के लिए, यदि इनपुट "zyzx" है, तो आउटपुट "xyzz" होगा।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• temp := s के आकार की सरणी, 0 से भरी हुई
• m := s का आकार - 1
• i को s के आकार -1 से -1 तक घटाते हुए करें:
  • यदि s[i] < s[m], तो m := i
  • temp[i] := m
• i को 0 से s के आकार तक के लिए करें:
  • a := temp[i]
  • यदि s[a], s[i] के बराबर नहीं है, तो:
    • s[:i] + s[a] + s[i+1:a] + s[i] + s[a+1:] वापस करें
• s वापस करें

उदाहरण

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