ধরুন আমাদের কাছে একটি স্ট্রিং আছে যা আমাদের সম্ভাব্য দীর্ঘতম সাবস্ট্রিংটি ফেরত দিতে হবে যাতে ঠিক k সংখ্যক অনন্য অক্ষর রয়েছে, যদি সম্ভাব্য দীর্ঘতম দৈর্ঘ্যের একাধিক সাবস্ট্রিং থাকে, তাদের যেকোনো একটি ফেরত দিন।
সুতরাং, যদি ইনপুটটি s ="ppqprqtqtqt", k =3 এর মত হয়, তাহলে আউটপুটটি rqtqtqt হবে কারণ এর দৈর্ঘ্য 7।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
N :=26
-
একটি ফাংশন সংজ্ঞায়িত করুন is_ok()। এটি গণনা করবে, k
-
val :=0
-
i 0 থেকে N রেঞ্জের জন্য, করুন
-
যদি গণনা [i]> 0 হয়, তাহলে
-
val :=val + 1
-
-
-
(k>=val)
হলে true ফেরত দিন -
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
অনন্য :=0, আকার :=s এর আকার
-
গণনা :=N আকারের একটি অ্যারে, 0 দিয়ে পূরণ করুন
-
আমি 0 থেকে আকারের রেঞ্জের জন্য, করুন
-
যদি s[i] এর গণনা 0 এর সমান হয়, তাহলে
-
অনন্য :=অনন্য + 1
-
-
1 দ্বারা s[i] গণনা বাড়ান
-
-
যদি অনন্য
-
এরকম কোন অক্ষর এবং প্রস্থান নেই
-
-
শুরু :=0, শেষ :=0
-
window_length :=1, window_start :=0
-
গণনা :=N আকারের একটি অ্যারে, 0 দিয়ে পূরণ করুন
-
1
দ্বারা s[0] এর গণনা বাড়ান -
আমি 1 থেকে আকারের রেঞ্জের জন্য, করুন
-
1 দ্বারা s[i] গণনা বাড়ান
-
end :=end + 1
-
যখন is_ok(count, k) মিথ্যা, do
-
1 দ্বারা s[i] গণনা হ্রাস করুন
-
start :=start + 1
-
-
যদি end-start+1> window_length, তারপর
-
window_length :=end-start+1
-
window_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
