Tìm chuỗi con dài nhất với k ký tự duy nhất trong một chuỗi đã cho bằng Python

Giả sử chúng ta có một chuỗi, chúng ta phải trả về chuỗi con dài nhất có thể có chính xác k số ký tự duy nhất, nếu có nhiều hơn một chuỗi con có độ dài dài nhất có thể, hãy trả về bất kỳ chuỗi nào trong số chúng.

Vì vậy, nếu đầu vào là s =​​"ppqprqtqtqt", k =3, thì đầu ra sẽ là rqtqtqt vì có độ dài 7.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• N:=26

• Định nghĩa một hàm is_ok (). Điều này sẽ được tính, k

• val:=0

• đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

  • nếu đếm [i]> 0 thì

    • val:=val + 1

• trả về true khi (k> =val)

• Từ phương thức chính, thực hiện như sau -

• unique:=0, size:=size of s

• count:=Một mảng kích thước N, điền bằng 0

• đối với tôi trong phạm vi từ 0 đến kích thước, hãy làm

  • nếu số s [i] bằng 0 thì

    • duy nhất:=unique + 1

  • tăng số s [i] lên 1

• nếu duy nhất

  • không có ký tự như vậy và thoát ra

• start:=0, end:=0

• window_length:=1, window_start:=0

• count:=Một mảng kích thước N, điền bằng 0

• tăng số s [0] lên 1

• đối với tôi trong phạm vi từ 1 đến kích thước, hãy làm

  • tăng số s [i] lên 1

  • end:=end + 1

  • trong khi is_ok (count, k) là false, thực hiện

    • giảm số s [i] đi 1

    • start:=start + 1

  • nếu end-start + 1> window_length, thì

    • window_length:=end-start + 1

    • window_start:=start

• trả về chuỗi con của s [từ chỉ mục window_start đến window_start + window_length]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"ppqprqtqtqt", 3

Đầu ra

rqtqtqt