पायथन में दिए गए स्ट्रिंग में k अद्वितीय वर्णों के साथ सबसे लंबा विकल्प खोजें

मान लीजिए कि हमारे पास एक स्ट्रिंग है जो हमें सबसे लंबे संभव सबस्ट्रिंग को वापस करना है जिसमें अद्वितीय वर्णों की संख्या 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