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

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

कोई भी इंडेक्स i चुनें और वर्ण pi और qi को स्वैप करें।
कोई भी इंडेक्स i चुनें और वर्ण pi और p(n-i-1) को स्वैप करें।
कोई भी इंडेक्स i चुनें और वर्ण qi और q(n-i-1) को स्वैप करें।

नोट - i का मान रेंज (0 ≤ i < n) में है।

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

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

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

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

उदाहरण

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

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"