मान लीजिए कि हमारे पास एक स्ट्रिंग है जो हमें सबसे लंबे संभव सबस्ट्रिंग को वापस करना है जिसमें अद्वितीय वर्णों की संख्या k है, यदि सबसे लंबी संभव लंबाई के एक से अधिक सबस्ट्रिंग हैं, तो उनमें से किसी को वापस कर दें।
इसलिए, यदि इनपुट s ="ppqprqtqtqt", k =3 जैसा है, तो आउटपुट rqtqtqt होगा क्योंकि इसकी लंबाई 7 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एन:=26
-
एक फ़ंक्शन परिभाषित करें is_ok() । यह गिनती लेगा, k
-
वैल:=0
-
मेरे लिए 0 से N की सीमा में, करें
-
अगर गिनती [i]> 0, तो
-
वैल:=वैल + 1
-
-
-
सही लौटें जब (k>=वैल)
-
मुख्य विधि से, निम्न कार्य करें -
-
अद्वितीय :=0, आकार :=s का आकार
-
गिनती :=आकार N की एक सरणी, 0 से भरें
-
मेरे लिए 0 से आकार की सीमा में, ऐसा करें
-
यदि s[i] की संख्या 0 के समान है, तो
-
अद्वितीय:=अद्वितीय + 1
-
-
s[i] की संख्या को 1 से बढ़ाएं
-
-
अगर अद्वितीय
-
ऐसा कोई वर्ण और निकास नहीं है
-
-
प्रारंभ:=0, अंत:=0
-
window_length :=1, window_start :=0
-
गिनती :=आकार N की एक सरणी, 0 से भरें
-
s[0] की संख्या में 1 तक वृद्धि करें
-
1 से आकार के बीच के लिए, करें
-
s[i] की संख्या को 1 से बढ़ाएं
-
अंत:=अंत + 1
-
जबकि is_ok(गिनती, k) गलत है, करें
-
s[i] की संख्या को 1 से कम करें
-
प्रारंभ:=प्रारंभ + 1
-
-
अगर एंड-स्टार्ट+1> window_length, तो
-
window_length :=एंड-स्टार्ट+1
-
window_start :=start
-
-
-
s का रिटर्न सबस्ट्रिंग [इंडेक्स विंडो_स्टार्ट से विंडो_स्टार्ट + विंडो_लेंथ]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
N = 26
def is_ok(count, k):
val = 0
for i in range(N):
if count[i] > 0:
val += 1
return (k >= val)
def k_unique_chars(s, k):
unique = 0
size = len(s)
count = [0] * N
for i in range(size):
if count[ord(s[i])-ord('a')] == 0:
unique += 1
count[ord(s[i])-ord('a')] += 1
if unique < k:
return "Not sufficient characters"
start = 0
end = 0
window_length = 1
window_start = 0
count = [0] * len(count)
count[ord(s[0])-ord('a')] += 1
for i in range(1,size):
count[ord(s[i])-ord('a')] += 1
end+=1
while not is_ok(count, k):
count[ord(s[start])-ord('a')] -= 1
start += 1
if end-start+1 > window_length:
window_length = end-start+1
window_start = start
return s[window_start:window_start + window_length]
s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k)) इनपुट
"ppqprqtqtqt", 3
आउटपुट
rqtqtqt
