Chương trình tìm chuỗi con awesome dài nhất trong Python

Cho chuỗi số s. Awesome substring: chuỗi con không rỗng có thể hoán vị thành palindrome. Tìm độ dài awesome substring dài nhất.

Ví dụ: s = "4353526", đầu ra = 5 ("35352" → hoán vị "35253" là palindrome).

Giải pháp

Bitmask theo dõi chẵn/lẻ tần suất chữ số (0-9). Palindrome <=> tối đa 1 bit = 1.

• n := 0 (bitmask hiện tại)
• pos_map := {0: len(s)} (vị trí đầu tiên gặp bitmask)
• max_len := 1
• Với i từ len(s)-1 xuống 0:
  • n ^= (1 << int(s[i]))
  • Nếu n trong pos_map: max_len = max(max_len, pos_map[n]-i)
  • Với j từ 0 đến 9: m = n ^ (1<
  • Nếu n không trong pos_map: pos_map[n] = i
• Trả về max_len

Ví dụ minh họa

Xem 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"

Đầu ra

5