पायथन में सबसे लंबा विस्मयकारी उपस्ट्रिंग ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास s नामक एक संख्यात्मक स्ट्रिंग है। जैसा कि हम जानते हैं, एक विस्मयकारी उपस्ट्रिंग s का एक गैर-खाली उपस्ट्रिंग है जैसे कि हम इसे पालिंड्रोम बनाने के लिए किसी भी संख्या में स्वैप कर सकते हैं। हमें s के अधिकतम लंबाई वाले विस्मयकारी उपस्ट्रिंग की लंबाई ज्ञात करनी है।

इसलिए, यदि इनपुट है s = "4353526", तो आउटपुट 5 होगा क्योंकि "35352" सबसे लंबा विस्मयकारी उपस्ट्रिंग है। हम "35253" पालिंड्रोम बना सकते हैं।

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

n := 0
pos_map := एक मैप जिसमें कुंजी 0 और संबंधित मान s का आकार है
max_len := 1
i को s के आकार - 1 से 0 तक, 1 से घटाकर, करें
- n := n XOR (2^s[i])
- यदि n pos_map में मौजूद है, तो
  - max_len := max_len और pos_map[n]-i का अधिकतम
- j को 0 से 9 तक के लिए, करें
  - m := n XOR 2^j
  - यदि m pos_map में है, तो
    - max_len := max_len और pos_map[m]-i का अधिकतम
- यदि n pos_map में नहीं है, तो
  - pos_map[n] := i
max_len वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(s):
    n = 0
    pos_map = {0: len(s)}
    max_len = 1
    for i in range(len(s)-1, -1, -1):
        n = n ^ (1 << int(s[i]))
        if n in pos_map:
            max_len = max(max_len, pos_map[n] - i)
        for j in range(10):
            m = n ^ (1 << j)
            if m in pos_map:
                max_len = max(max_len, pos_map[m] - i)
        if n not in pos_map:
            pos_map[n] = i
    return max_len

s = "4353526"
print(solve(s))

इनपुट

"4353526"