Chương trình tìm chuỗi con tuyệt vời dài nhất bằng Python

Giả sử chúng ta có một chuỗi số s. Như chúng ta đã biết, một chuỗi con tuyệt vời là một chuỗi con không rỗng của s để chúng ta có thể thực hiện bất kỳ số lượng hoán đổi nào để biến nó thành palindrome. Chúng ta phải tìm độ dài của chuỗi con tuyệt vời có độ dài lớn nhất là s.

Vì vậy, nếu đầu vào là s ="4353526", thì đầu ra sẽ là 5 vì "35352" là chuỗi con tuyệt vời dài nhất. chúng ta có thể tạo ra "35253" palindrome.

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

n:=0
pos_map:=một bản đồ chứa khóa 0 và giá trị tương ứng có kích thước là s
max_len:=1
đối với tôi trong phạm vi kích thước từ s - 1 đến 0, giảm đi 1, thực hiện
- n:=n XOR (2 ^ s [i])
- nếu n có trong pos_map thì
  - max_len:=tối đa của max_len và pos_map [n] -i
- đối với j trong phạm vi từ 0 đến 9, thực hiện
  - m:=n XOR 2 ^ j
  - nếu m ở trong pos_map, thì
    - max_len:=tối đa của max_len và pos_map [m] -i
- nếu n không có trong pos_map, thì
  - pos_map [n]:=i
trả về max_len

Ví dụ

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

def solve(s):
   n = 0
   pos_map = {0:len(s)}

   max_len = 1

   for i in range(len(s)-1, -1, -1):
      n = n ^ (1 << int(s[i]))

      if n in pos_map:
         max_len = max(max_len, pos_map[n]-i)

      for j in range(10):
         m = n ^ (1 << j)
         if m in pos_map:
            max_len = max(max_len, pos_map[m]-i)

      if n not in pos_map:
         pos_map[n] = i

   return max_len

s = "4353526"
print(solve(s))

Đầu vào

"4353526"

Chương trình tìm chuỗi con tuyệt vời dài nhất bằng Python

Ví dụ

Đầu vào

Đầu ra