पायथन में दो स्ट्रिंग्स को बराबर बनाने के लिए आवश्यक प्रीप्रोसेस चालों की न्यूनतम संख्या ज्ञात करें

मान लीजिए कि हमारे पास समान लंबाई के दो स्ट्रिंग्स P और Q हैं, जिनमें केवल लोअर केस लेटर्स हैं, हमें स्ट्रिंग P पर प्री-प्रोसेसिंग मूव्स की न्यूनतम संख्या को गिनना होगा, इसे नीचे के ऑपरेशनों को लागू करने के बाद स्ट्रिंग Q के बराबर बनाने के लिए आवश्यक है -

कोई भी अनुक्रमणिका i चुनें और वर्ण pi और qi स्वैप करें।
कोई भी अनुक्रमणिका i चुनें और वर्ण pi और pn – i – 1 स्वैप करें।
कोई भी अनुक्रमणिका i चुनें और वर्ण qi और qn – i – 1. स्वैप करें।

नोट - रेंज में i का मान (0 i

एक चाल में हम अंग्रेजी वर्णमाला के किसी अन्य वर्ण के साथ P के किसी वर्ण को बदल सकते हैं।

इसलिए, यदि इनपुट P ="pqprpqp", Q ="qprpqpp" जैसा है, तो आउटपुट 4 होगा जैसे कि हम P0 ='q', P2 ='r', P3 ='p' और P4 ='सेट करते हैं। q' और P "qqrpqqp" होगा। उसके बाद हम संचालन के निम्नलिखित अनुक्रम द्वारा समान तार प्राप्त कर सकते हैं:स्वैप (P1, Q1) और स्वैप (P1, P5)।

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

n :=P का आकार
रेस :=0
मैं के लिए 0 से n / 2 की सीमा में, करते हैं
- my_map :=एक नया नक्शा
- my_map[P[i]] :=1
- यदि P[i], P[n - i - 1] के समान है, तो
  - my_map[P[n - i - 1]] :=my_map[P[n - i - 1]] + 1
- अगर Q[i] my_map में है, तो
  - my_map[Q[i]] :=my_map[Q[i]] + 1
- अन्यथा,
  - my_map[Q[i]] :=1
- अगर Q[n - i - 1] my_map में है, तो
  - my_map[Q[n - 1 - i]] :=my_map[Q[n - 1 - i]] + 1
- अन्यथा,
  - my_map[Q[n - 1 - i]] :=1
- आकार :=my_map का आकार
- अगर आकार 4 के समान है, तो
  - रेस :=रेस + 2
- अन्यथा जब आकार 3 के समान हो, तब
  - res :=res + 1 + (1 जब (P[i] P[n - i - 1] के समान हो), अन्यथा 0)
- अन्यथा जब आकार 2 के समान हो, तब
  - res :=res + my_map[P[i]] 2 के समान नहीं है
यदि n mod 2 1 के समान है और P[n / 2] Q[n / 2] के समान नहीं है, तो
- रेस :=रेस + 1
रिटर्न रेस

उदाहरण

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

def count_preprocess(P, Q):
   n = len(P)
   res = 0
   for i in range(n // 2):
      my_map = dict()
      my_map[P[i]] = 1
      if P[i] == P[n - i - 1]:
         my_map[P[n - i - 1]] += 1
      if Q[i] in my_map:
         my_map[Q[i]] += 1
      else:
         my_map[Q[i]] = 1
      if Q[n - i - 1] in my_map:
         my_map[Q[n - 1 - i]] += 1
      else:
         my_map[Q[n - 1 - i]] = 1
      size = len(my_map)
      if (size == 4):
         res += 2
      elif (size == 3):
         res += 1 + (P[i] == P[n - i - 1])
      elif (size == 2):
         res += my_map[P[i]] != 2
   if (n % 2 == 1 and P[n // 2] != Q[n // 2]):
      res += 1
   return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

इनपुट

"pqprpqp", "qprpqpp"