मान लीजिए हमारे पास केवल लोअरकेस अक्षरों वाली दो स्ट्रिंग्स s और t हैं। एक ऑपरेशन में, हम s या t में किसी भी कैरेक्टर को किसी भी लोअरकेस अक्षर में बदल सकते हैं। हमें निम्नलिखित तीन शर्तों में से एक को पूरा करना है:
sका हर अक्षर वर्णमाला मेंtके हर अक्षर से सख्ती से छोटा हो।tका हर अक्षर वर्णमाला मेंsके हर अक्षर से सख्ती से छोटा हो।sऔरtदोनों में केवल एक विशिष्ट अक्षर हो।
हमें परिणाम प्राप्त करने के लिए आवश्यक न्यूनतम ऑपरेशन्स की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट s = "sts", t = "uss" है, तो आउटपुट 2 होगा क्योंकि:
- यदि हम
tको 2 ऑपरेशन में"uuu"में बदलते हैं, तोsका हर अक्षरtके हर अक्षर से छोटा होता है। - यदि हम
sको"ttt"औरtको"sss"में 3 ऑपरेशन में बदलते हैं, तोtका हर अक्षरsके हर अक्षर से छोटा होता है। - यदि हम
sको"sss"औरtको"sss"में 2 ऑपरेशन में बदलते हैं, तोsऔरtमें एक विशिष्ट अक्षर होता है।
यहां सबसे अच्छा तरीका 2 ऑपरेशन में किया गया था (या तो 1 या 3)।
हल करने के चरण
counter_s :=sमें प्रत्येक कैरेक्टर की फ्रीक्वेंसी रखने के लिए मैपcounter_t :=tमें प्रत्येक कैरेक्टर की फ्रीक्वेंसी रखने के लिए मैपless_s := infinity,less_t := infinity,unique := infinityaccu_s := 0,accu_t := 0- लोअरकेस अंग्रेजी कैरेक्टर में प्रत्येक
cके लिए:unique := min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])- यदि
c > 'a', तो:less_s := min(less_s, len(s) - accu_s + accu_t)less_t := min(less_t, len(t) - accu_t + accu_s)
accu_s += counter_s[c]accu_t += counter_t[c]
less_s, less_t, uniqueका न्यूनतम वापस करें।
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
from collections import Counter
import string
def solve(s, t):
counter_s = Counter(s)
counter_t = Counter(t)
less_s, less_t, unique = float('inf'), float('inf'), float('inf')
accu_s, accu_t = 0, 0
for c in string.ascii_lowercase:
unique = min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
if c > 'a':
less_s = min(less_s, len(s) - accu_s + accu_t)
less_t = min(less_t, len(t) - accu_t + accu_s)
accu_s += counter_s[c]
accu_t += counter_t[c]
return min(less_s, less_t, unique)
s = "sts"
t = "uss"
print(solve(s, t))
इनपुट
"sts", "uss"
आउटपुट
2
