पायथन में सबसे लंबे समय तक भयानक सबस्ट्रिंग खोजने का कार्यक्रम

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

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

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

n :=0
pos_map :=एक कुंजी 0 और संबंधित मान वाला नक्शा s के आकार का होता है
max_len :=1
मैं के लिए s - 1 से 0 के श्रेणी आकार में, 1 से घटाएं
- n :=n XOR (2^s[i])
- अगर n pos_map में मौजूद है, तो
  - max_len:=max_len और pos_map की अधिकतम[n]-i
- j के लिए 0 से 9 की सीमा में, करें
  - एम:=एन एक्सओआर 2^जे
  - अगर 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"