मान लीजिए हमारे पास एक स्ट्रिंग है हमें सबसे लंबा संभव सबस्ट्रिंग लौटाना है जिसमें ठीक k संख्या में अद्वितीय वर्ण हों, यदि सबसे लंबी संभव लंबाई के एक से अधिक सबस्ट्रिंग हैं, तो उनमें से कोई भी लौटाएं।
तो, यदि इनपुट s = "ppqprqtqtqt", k = 3 जैसा है, तो आउटपुट rqtqtqt होगा क्योंकि इसकी लंबाई 7 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
N := 26
is_ok() फंक्शन परिभाषित करें। यह count, k लेगा।
val := 0
i को 0 से N तक के लिए, करें:
यदि count[i] > 0, तो:
val := val + 1
तब सच लौटाएं जब (k >= val)
मुख्य विधि से, निम्नलिखित करें:
unique := 0, size := s का आकार
count := आकार N का एक ऐरे, 0 से भरा हुआ
i को 0 से size तक के लिए, करें:
यदि s[i] की गिनती 0 के समान है, तो:
unique := unique + 1
s[i] की गिनती को 1 से बढ़ाएं
यदि unique < k, तो:
ऐसा कोई वर्ण नहीं है और बाहर निकलें
start := 0, end := 0
window_length := 1, window_start := 0
count := आकार N का एक ऐरे, 0 से भरा हुआ
s[0] की गिनती को 1 से बढ़ाएं
i को 1 से size तक के लिए, करें:
s[i] की गिनती को 1 से बढ़ाएं
end := end + 1
जब is_ok(count, k) गलत है, करें:
s[i] की गिनती को 1 से घटाएं
start := start + 1
यदि end-start+1 > window_length, तो:
window_length := end-start+1
window_start := start
s[window_start से window_start + window_length इंडेक्स तक] का सबस्ट्रिंग लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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
