Chương trình tìm chuỗi con lớn nhất giữa hai ký tự bằng nhau trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm độ dài của chuỗi con dài nhất giữa hai chữ cái hoặc phần tử bằng nhau, không kể hai ký tự. Nếu chúng ta không thể tìm thấy chuỗi con như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là s =​​"level", thì đầu ra sẽ là 3 vì các chuỗi con tối ưu có thể là "lev" hoặc "vel".

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

• memo:=a new map

• đối với tôi trong phạm vi từ 0 đến kích thước của s-1, hãy thực hiện

  • nếu s [i] ở trong bản ghi nhớ thì

    • chèn i vào cuối bản ghi nhớ [s [i]]

  • nếu không,

    • memo [s [i]]:=danh sách chỉ có một phần tử i

• tốt nhất:=0

• đối với mỗi khóa trong bản ghi nhớ, hãy thực hiện

  • tốt nhất:=tối đa trong tổng số tốt nhất và (phần tử cuối cùng của bản ghi nhớ [key] - phần tử đầu tiên của bản ghi nhớ [key])

• trở lại tốt nhất - 1

Ví dụ (Python)

def solve(s):
   memo = {}
   for i in range(len(s)):
      if s[i] in memo:
         memo[s[i]].append(i)
      else:
         memo[s[i]] = [i]

   best = 0
   for key in memo:
      best = max(best, memo[key][-1] - memo[key][0])
   return best - 1

s = "level"
print(solve(s))

Đầu vào

"level"

Đầu ra

3