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

Giả sử ta có chuỗi s, tìm độ dài chuỗi con dài nhất giữa hai ký tự bằng nhau, không tính hai ký tự đó. Nếu không tìm thấy, trả về -1.

Ví dụ: s = "level", kết quả 3 vì chuỗi con tối ưu là "lev" hoặc "vel".

Giải thuật

1. memo := {} (map ký tự → danh sách chỉ mục)
2. For i từ 0 đến len(s)-1:
   • Nếu s[i] trong memo: thêm i vào memo[s[i]]
   • Ngược lại: memo[s[i]] = [i]
3. best := 0
4. Với mỗi key trong memo:
   • best := max(best, memo[key][-1] - memo[key][0])
5. Trả về best - 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))

Input

"level"

Output

3