Python - Chuỗi con tăng liên tiếp dài nhất bắt đầu bằng 'a' có thể thay '?'

Cho chuỗi s chứa chữ thường và ký tự '?'. Mỗi '?' có thể xóa hoặc thay bằng bất kỳ chữ thường nào. Tìm độ dài chuỗi con liên tiếp tăng dần (ví dụ: "abcde...") dài nhất bắt đầu bằng 'a'.

Ví dụ

Input: s = "vta???defke"
Output: 6
Giải thích: Thay '???' thành 'bcd' → "vtabcdefke", chuỗi "abcdef" dài 6.

Thuật toán: Duyệt 1 lần với trạng thái

Duy trì 3 biến khi duyệt chuỗi:

• length: độ dài chuỗi tăng hiện tại kết thúc tại ký tự trước
• qmarks: số '?' liên tiếp vừa gặp
• maxlen: kết quả tối đa

Khi gặp ký tự thường c (không phải '?'):

• idx = ord(c) - ord('a') (vị trí trong bảng chữ cái, a=0, b=1...)
• Cập nhật length:
  • Nếu length ≤ idx ≤ length + qmarks: có thể dùng '?' để lấp đầy khoảng trống → length = idx + 1
  • Nếu idx ≤ qmarks: có thể bắt đầu mới từ 'a' dùng '?' → length = idx + 1
  • Ngược lại: đứt gãy → length = 0
• Reset qmarks = 0
• Cập nhật maxlen = max(maxlen, min(length + qmarks, 26)) (tối đa 26 chữ cái)

Mã Python

def solve(s):
    maxlen = length = qmarks = 0
    for c in s:
        if c == "?":
            qmarks += 1
        else:
            idx = ord(c) - ord("a")
            # Có thể tiếp tục chuỗi tăng hiện tại?
            if length <= idx <= length + qmarks or idx <= qmarks:
                length = idx + 1
            else:
                length = 0
            qmarks = 0
        maxlen = max(maxlen, min(length + qmarks, 26))
    return maxlen

# Test
s = "vta???defke"
print(solve(s))  # Output: 6

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt chuỗi 1 lần
• Không gian: O(1) - chỉ dùng vài biến

Lưu ý: Giới hạn 26 do bảng chữ cái tiếng Anh chỉ có 26 chữ cái. Thuật toán tham lam này hoạt động vì ta luôn cố gắng kéo dài chuỗi tăng hiện tại hoặc bắt đầu mới tối ưu.