मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है जिसकी लंबाई सम है। हमें उन वर्णों की न्यूनतम संख्या ज्ञात करनी है जिन्हें अपडेट करने की आवश्यकता है ताकि निम्न तीन शर्तों में से एक सभी i के लिए पूरी हो, जहां 0 ≤ i < n/2 और j, n/2 ≤ j < n:
- s[i] > s[j]
- s[i] < s[j]
- s[i] == s[j]
इसलिए, यदि इनपुट s = "pppxxp" है, तो आउटपुट 1 होगा क्योंकि यदि हम अंतिम "p" को "x" में बदलते हैं, तो यह शर्त s[i] < s[j] को संतुष्ट कर सकता है।
हल करने का दृष्टिकोण
- n := s का आकार
- left := s के बाएं आधे भाग के प्रत्येक वर्ण की आवृत्तियों वाला शब्दकोश
- right := s के दाएं आधे भाग के प्रत्येक वर्ण की आवृत्तियों वाला शब्दकोश
- ans := n
- लोअरकेस अंग्रेजी अक्षरों में प्रत्येक वर्ण pivot के लिए, करें:
- ans := ans और (n - left[pivot] - right[pivot]) का न्यूनतम
- good := left[c] में मौजूद सभी तत्वों का योग जहां c <= pivot
- good := good + right[c] में मौजूद सभी तत्वों का योग जहां c > pivot
- ans := ans और (n - good) का न्यूनतम
- good := left[c] में मौजूद सभी तत्वों का योग जहां c > pivot
- good := good + right[c] में मौजूद सभी तत्वों का योग जहां c <= pivot
- ans := ans और (n - good) का न्यूनतम
- ans लौटाएं
उदाहरण
from collections import Counter
from string import ascii_lowercase
def solve(s):
n = len(s)
left = Counter(s[: n >> 1])
right = Counter(s[n >> 1 :])
ans = n
for pivot in ascii_lowercase:
ans = min(ans, n - left[pivot] - right[pivot])
good = sum(left[c] for c in left if c <= pivot)
good += sum(right[c] for c in right if c > pivot)
ans = min(ans, n - good)
good = sum(left[c] for c in left if c > pivot)
good += sum(right[c] for c in right if c <= pivot)
ans = min(ans, n - good)
return ans
s = "pppxxp"
print(solve(s))इनपुट
"pppxxp"
आउटपुट
1
