Chương trình tìm độ dài dãy con liền kề dài nhất cùng chữ cái đầu trong Python

Cho danh sách các chuỗi chữ thường words. Tìm độ dài dãy con liền kề dài nhất mà mọi từ trong dãy đều có cùng chữ cái đầu tiên.

Ví dụ: words = ["she", "sells", "seashells", "on", "the", "sea", "shore"] → kết quả 3. Dãy con: ["she", "sells", "seashells"] đều bắt đầu bằng 's'.

Thuật toán giải quyết (O(n))

1. Khởi tạo cnt = 1, maxcnt = 0, prev_char = ""
2. Duyệt từng word trong words:
   • Nếu prev_char rỗng: gán prev_char = word[0]
   • Nếu word[0] == prev_char: cnt += 1
   • Ngược lại: prev_char = word[0], cnt = 1
   • Cập nhật maxcnt = max(maxcnt, cnt)
3. Trả về maxcnt

Ví dụ minh họa

def solve(words):
    cnt = 1
    maxcnt = 0
    prev_char = ""
    for word in words:
        if prev_char == "":
            prev_char = word[0]
        elif prev_char == word[0]:
            cnt += 1
        else:
            prev_char = word[0]
            cnt = 1
        maxcnt = max(maxcnt, cnt)
    return maxcnt

words = ["she", "sells", "seashells", "on", "the", "sea", "shore"]
print(solve(words))

Đầu vào

["she", "sells", "seashells", "on", "the", "sea", "shore"]

Đầu ra

3