मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें दो समान अक्षरों या तत्वों के बीच सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है, उन दो कैरेक्टर्स को छोड़कर। यदि हम ऐसा सबस्ट्रिंग नहीं ढूंढ सकते, तो -1 वापस करें।
इसलिए, यदि इनपुट है: s = "level", तो आउटपुट 3 होगा क्योंकि इष्टतम सबस्ट्रिंग या तो "lev" या "vel" हो सकते हैं।
हल करने के चरण
- memo := एक नया मैप
- i को 0 से s के आकार - 1 तक के लिए:
- यदि s[i], memo में है, तो i को memo[s[i]] के अंत में डालें
- अन्यथा, memo[s[i]] := केवल i तत्व वाली सूची
- best := 0
- memo में प्रत्येक key के लिए: best := max(best, memo[key][-1] - memo[key][0])
- best - 1 वापस करें
उदाहरण (Python)
def solve(s):
memo = {}
for i in range(len(s)):
if s[i] in memo:
memo[s[i]].append(i)
else:
memo[s[i]] = [i]
best = 0
for key in memo:
best = max(best, memo[key][-1] - memo[key][0])
return best - 1
s = "level"
print(solve(s))
इनपुट
"level"
आउटपुट
3
