Bài 7.3 - Python và kỹ thuật Sliding window

Trong thế giới giải thuật và cấu trúc dữ liệu, việc xử lý các mảng hoặc chuỗi dài có thể gây ra những thách thức lớn về hiệu năng. Đặc biệt, khi chúng ta cần tìm kiếm hoặc tính toán trên các đoạn con (subarray) hoặc chuỗi con (substring) liên tục, một cách tiếp cận "thô bạo" (brute-force) thường liên quan đến các vòng lặp lồng nhau, dẫn đến độ phức tạp O(n^2) hoặc thậm chí cao hơn.

May mắn thay, tồn tại một kỹ thuật cực kỳ thanh lịch và hiệu quả để giải quyết loại bài toán này: Kỹ thuật Sliding window (Cửa sổ trượt). Đây không phải là một cấu trúc dữ liệu mới, mà là một mẫu thiết kế giải thuật (algorithmic design pattern).

Kỹ Thuật Sliding Window là gì?

Hãy tưởng tượng bạn có một dãy dữ liệu dài (một mảng hoặc một chuỗi) và bạn cần phân tích một phần liên tục của nó tại một thời điểm. Thay vì kiểm tra mọi đoạn con có thể có (điều này rất tốn kém), kỹ thuật Sliding window đề xuất một cách tiếp cận thông minh hơn:

Xác định một "cửa sổ": Đây là một đoạn con hoặc chuỗi con liên tục trong dữ liệu gốc. Cửa sổ này được xác định bởi hai điểm mốc: một điểm bắt đầu (thường gọi là left hoặc start) và một điểm kết thúc (thường gọi là right hoặc end).
Trượt cửa sổ: Cửa sổ này sẽ "trượt" qua dãy dữ liệu. Quá trình trượt thường bao gồm:
- Mở rộng cửa sổ: Di chuyển điểm kết thúc (right) về phía trước để thêm một phần tử mới vào cửa sổ.
- Thu hẹp cửa sổ: Dựa trên một điều kiện cụ thể của bài toán, di chuyển điểm bắt đầu (left) về phía trước để loại bỏ phần tử cũ ra khỏi cửa sổ.
Tính toán trong cửa sổ: Tại mỗi bước, bạn sẽ thực hiện các phép tính hoặc kiểm tra cần thiết bên trong cửa sổ hiện tại.

Điểm mấu chốt làm cho kỹ thuật này hiệu quả là thay vì tính toán lại từ đầu cho mỗi đoạn con, chúng ta chỉ cập nhật kết quả dựa trên sự thay đổi nhỏ khi cửa sổ trượt (thêm một phần tử, bớt một phần tử). Điều này cho phép chúng ta duyệt qua dữ liệu chỉ một lần với hai con trỏ left và right, giảm độ phức tạp tính toán xuống còn O(n) (trong hầu hết các trường hợp, giả sử các thao tác trong cửa sổ như thêm/bớt/tra cứu là O(1) hoặc O(log k) nơi k là kích thước cửa sổ, nhưng tổng thể vẫn hiệu quả hơn O(n^2)).

Kỹ thuật Sliding window có thể được chia làm hai loại chính:

Cửa sổ có kích thước cố định: Kích thước của cửa sổ (right - left + 1) luôn giữ nguyên trong suốt quá trình trượt.
Cửa sổ có kích thước thay đổi: Kích thước của cửa sổ thay đổi tùy thuộc vào điều kiện của bài toán.

Chúng ta hãy cùng đi sâu vào các ví dụ minh họa trong Python để thấy rõ sức mạnh và cách áp dụng của kỹ thuật này.

Ví Dụ 1: Tìm Tổng Lớn Nhất của Đoạn Con Kích Thước K (Cửa sổ cố định)

Đây là bài toán kinh điển để bắt đầu với Sliding window.

Bài toán: Cho một mảng các số nguyên arr và một số nguyên dương k. Tìm tổng lớn nhất của một đoạn con liên tục trong arr có kích thước đúng bằng k.

Phân tích: Cách "thô bạo" sẽ là duyệt qua tất cả các đoạn con có kích thước k (bắt đầu từ index 0, 1, ..., n-k) và tính tổng của từng đoạn, sau đó tìm giá trị tổng lớn nhất. Điều này cần một vòng lặp bên ngoài chạy n-k+1 lần và một vòng lặp bên trong tính tổng k phần tử. Độ phức tạp là O(n * k), hoặc O(n^2) trong trường hợp k gần bằng n.

Với kỹ thuật Sliding window, chúng ta chỉ cần duyệt qua mảng một lần.

Áp dụng Sliding Window:

Tính tổng của đoạn con đầu tiên có kích thước k (từ index 0 đến k-1). Lưu giá trị này vào biến max_sum (kết quả lớn nhất tìm được) và current_sum (tổng của cửa sổ hiện tại).
Bắt đầu trượt cửa sổ. Duyệt từ index k đến cuối mảng (n-1).
Tại mỗi bước (khi điểm right đang ở index i):
- Thêm phần tử mới arr[i] vào current_sum.
- Bớt phần tử cũ arr[i-k] (phần tử vừa rời khỏi cửa sổ ở bên trái) khỏi current_sum.
- Cập nhật max_sum nếu current_sum hiện tại lớn hơn.
Sau khi duyệt hết mảng, max_sum chính là kết quả cần tìm.

Code minh họa:

def max_sum_subarray_of_size_k(arr, k):
    """
    Tìm tổng lớn nhất của đoạn con liên tục kích thước k.
    Sử dụng kỹ thuật Sliding window.
    """
    n = len(arr)
    # Kiểm tra điều kiện đầu vào
    if k > n:
        return "Kích thước k lớn hơn kích thước mảng."

    # 1. Tính tổng của cửa sổ đầu tiên (từ 0 đến k-1)
    # Khởi tạo current_sum và max_sum
    current_sum = sum(arr[:k])
    max_sum = current_sum

    # left pointer sẽ bắt đầu từ 0 sau khi cửa sổ đầu tiên được xử lý
    left = 0 # Con trỏ trái

    # right pointer sẽ bắt đầu từ k
    # Bắt đầu trượt cửa sổ từ index k đến hết mảng
    for right in range(k, n):
        # 2. Mở rộng cửa sổ: Thêm phần tử mới ở bên phải
        current_sum += arr[right]

        # 3. Thu hẹp cửa sổ: Bớt phần tử cũ ở bên trái
        # Phần tử rời đi là arr[left]. Sau đó tăng left lên 1.
        current_sum -= arr[left]
        left += 1

        # 4. Cập nhật max_sum với tổng hiện tại của cửa sổ
        max_sum = max(max_sum, current_sum)

    return max_sum

# Ví dụ sử dụng
arr1 = [2, 1, 5, 1, 3, 2]
k1 = 3
print(f"Mảng: {arr1}, k: {k1}")
print(f"Tổng lớn nhất của đoạn con kích thước {k1}: {max_sum_subarray_of_size_k(arr1, k1)}") # Output: 9 (đoạn [5, 1, 3])

arr2 = [2, 3, 4, 1, 5]
k2 = 2
print(f"Mảng: {arr2}, k: {k2}")
print(f"Tổng lớn nhất của đoạn con kích thước {k2}: {max_sum_subarray_of_size_k(arr2, k2)}") # Output: 7 (đoạn [3, 4])

Giải thích Code:

Chúng ta khởi tạo current_sum bằng tổng của k phần tử đầu tiên. max_sum ban đầu cũng bằng giá trị này.
Con trỏ left ban đầu không cần thiết để tính tổng đầu tiên, nhưng nó sẽ chỉ vào phần tử đầu tiên của cửa sổ khi chúng ta bắt đầu trượt (sau khi tính tổng đầu tiên, left sẽ trỏ đến index 0).
Vòng lặp for right in range(k, n): bắt đầu con trỏ right từ index k. Đây là phần tử đầu tiên nằm ngoài cửa sổ ban đầu, chuẩn bị được thêm vào.
Bên trong vòng lặp, current_sum += arr[right] thêm phần tử mới vào tổng hiện tại.
current_sum -= arr[left] bớt phần tử cũ (phần tử tại left) ra khỏi tổng.
left += 1 di chuyển con trỏ left về phía trước, "trượt" cửa sổ sang phải.
max_sum = max(max_sum, current_sum) đảm bảo chúng ta luôn lưu trữ tổng lớn nhất gặp được.
Sau mỗi lần lặp, cửa sổ từ left đến right (arr[left:right+1]) luôn có kích thước k.

Cách làm này chỉ duyệt mảng một lần, thực hiện các phép cộng/trừ O(1) cho mỗi phần tử, nên độ phức tạp là O(n), hiệu quả hơn đáng kể so với O(n*k).

Ví Dụ 2: Tìm Chiều Dài Chuỗi Con Dài Nhất Không Có Ký Tự Lặp Lại (Cửa sổ thay đổi)

Đây là một bài toán phổ biến minh họa kỹ thuật Sliding window với kích thước cửa sổ thay đổi.

Bài toán: Cho một chuỗi s, tìm chiều dài của chuỗi con liên tục dài nhất mà không có bất kỳ ký tự nào lặp lại.

Phân tích: Cách "thô bạo" sẽ là kiểm tra mọi chuỗi con (có O(n^2) chuỗi con), và với mỗi chuỗi con, kiểm tra xem nó có ký tự lặp lại không (có thể dùng set, mất O(k) hoặc O(k log k) tùy cài đặt, với k là chiều dài chuỗi con). Tổng cộng độ phức tạp có thể lên đến O(n^3) hoặc O(n^2).

Với Sliding window, chúng ta có thể giảm xuống O(n).

Áp dụng Sliding Window:

Duy trì một cửa sổ được định nghĩa bởi left và right.
Sử dụng một tập hợp (set) hoặc từ điển (dictionary) để lưu trữ các ký tự hiện có trong cửa sổ để kiểm tra sự lặp lại một cách hiệu quả (O(1) trung bình).
Di chuyển con trỏ right để mở rộng cửa sổ, thêm ký tự s[right] vào cửa sổ (và vào set/dictionary).
Nếu ký tự s[right] đã tồn tại trong cửa sổ (tức là đã có trong set/dictionary), điều này có nghĩa là cửa sổ hiện tại chứa ký tự lặp lại và không hợp lệ. Chúng ta cần thu hẹp cửa sổ từ bên trái bằng cách di chuyển con trỏ left về phía trước, loại bỏ ký tự s[left] khỏi cửa sổ (và khỏi set/dictionary), cho đến khi cửa sổ trở nên hợp lệ trở lại (tức là không còn ký tự lặp lại nữa).
Tại mỗi bước khi cửa sổ hợp lệ, chúng ta tính chiều dài hiện tại của cửa sổ (right - left + 1) và cập nhật chiều dài lớn nhất tìm được cho đến nay.

Code minh họa:

def length_of_longest_substring(s):
    """
    Tìm chiều dài của chuỗi con liên tục dài nhất không có ký tự lặp lại.
    Sử dụng kỹ thuật Sliding window.
    """
    n = len(s)
    if n == 0:
        return 0

    # Sử dụng set để lưu trữ các ký tự trong cửa sổ hiện tại (giúp kiểm tra O(1))
    char_set = set()
    # Con trỏ trái của cửa sổ
    left = 0
    # Chiều dài lớn nhất tìm được
    max_length = 0

    # right pointer duyệt qua toàn bộ chuỗi để mở rộng cửa sổ
    for right in range(n):
        # Khi nào cửa sổ không hợp lệ (ký tự tại right đã có trong cửa sổ)?
        # Chúng ta cần thu hẹp cửa sổ từ bên trái
        while s[right] in char_set:
            # Loại bỏ ký tự ở bên trái ra khỏi set và di chuyển con trỏ trái
            char_set.remove(s[left])
            left += 1

        # Bây giờ cửa sổ đã hợp lệ (ký tự tại right chưa có)
        # Thêm ký tự tại right vào set và mở rộng cửa sổ
        char_set.add(s[right])

        # Cập nhật chiều dài lớn nhất
        # Chiều dài cửa sổ hiện tại là (right - left + 1)
        max_length = max(max_length, right - left + 1)

    return max_length

# Ví dụ sử dụng
s1 = "abcabcbb"
print(f"Chuỗi: \"{s1}\"")
print(f"Chiều dài chuỗi con dài nhất không lặp lại: {length_of_longest_substring(s1)}") # Output: 3 (abc)

s2 = "bbbbb"
print(f"Chuỗi: \"{s2}\"")
print(f"Chiều dài chuỗi con dài nhất không lặp lại: {length_of_longest_substring(s2)}") # Output: 1 (b)

s3 = "pwwkew"
print(f"Chuỗi: \"{s3}\"")
print(f"Chiều dài chuỗi con dài nhất không lặp lại: {length_of_longest_substring(s3)}") # Output: 3 (wke hoặc kew)

s4 = ""
print(f"Chuỗi: \"{s4}\"")
print(f"Chiều dài chuỗi con dài nhất không lặp lại: {length_of_longest_substring(s4)}") # Output: 0

Giải thích Code:

Chúng ta sử dụng một set (char_set) để theo dõi các ký tự trong cửa sổ hiện tại. Việc thêm (add), xóa (remove) và kiểm tra sự tồn tại (in) trên set có độ phức tạp trung bình là O(1).
left và right là hai con trỏ của cửa sổ. right luôn tiến về phía trước bằng vòng lặp for.
Vòng lặp while s[right] in char_set: là nơi logic thu hẹp cửa sổ diễn ra. Nếu ký tự mới s[right] đã có trong char_set (tức là có ký tự lặp lại trong cửa sổ), chúng ta sẽ liên tục xóa phần tử ở left khỏi char_set và tăng left lên cho đến khi ký tự s[right] không còn lặp lại trong cửa sổ nữa.
Sau khi vòng lặp while kết thúc (đảm bảo cửa sổ hiện tại không có ký tự lặp lại), chúng ta thêm s[right] vào char_set.
Chúng ta cập nhật max_length bằng chiều dài hiện tại của cửa sổ (right - left + 1).
Cả hai con trỏ left và right chỉ duyệt qua chuỗi một lần. Các thao tác trên set là O(1). Do đó, độ phức tạp tổng thể là O(n).

Ví Dụ 3: Tìm Chiều Dài Đoạn Con Có Tổng Lớn Hơn Hoặc Bằng S Nhỏ Nhất (Cửa sổ thay đổi)

Một ví dụ khác về cửa sổ có kích thước thay đổi, tập trung vào việc thỏa mãn một điều kiện về tổng.

Bài toán: Cho một mảng các số nguyên dương nums và một số nguyên dương target. Tìm chiều dài nhỏ nhất của một đoạn con liên tục có tổng lớn hơn hoặc bằng target. Nếu không có đoạn con nào như vậy, trả về 0.

Phân tích: Cách "thô bạo" là kiểm tra tất cả các đoạn con, tính tổng của chúng và tìm đoạn con hợp lệ có chiều dài nhỏ nhất. Có O(n^2) đoạn con. Tính tổng mỗi đoạn mất O(n), hoặc O(1) nếu tính toán trước tổng tiền tố, nhưng vẫn cần O(n^2) để duyệt.

Sử dụng Sliding window, chúng ta có thể giải quyết bài toán này trong O(n).

Áp dụng Sliding Window:

Duy trì một cửa sổ bằng hai con trỏ left và right.
Duy trì current_sum là tổng của các phần tử trong cửa sổ hiện tại.
Di chuyển con trỏ right để mở rộng cửa sổ, thêm nums[right] vào current_sum.
Trong khi current_sum lớn hơn hoặc bằng target:
- Cửa sổ hiện tại là một ứng viên cho đáp án. Tính chiều dài của nó (right - left + 1) và cập nhật chiều dài nhỏ nhất tìm được cho đến nay.
- Để tìm chiều dài nhỏ nhất, chúng ta cố gắng thu hẹp cửa sổ từ bên trái. Loại bỏ nums[left] khỏi current_sum và di chuyển left về phía trước. Tiếp tục quá trình thu hẹp này cho đến khi current_sum nhỏ hơn target (tức là cửa sổ không còn hợp lệ).
Tiếp tục mở rộng cửa sổ với right cho đến hết mảng.
Nếu tìm thấy ít nhất một đoạn con thỏa mãn, kết quả là chiều dài nhỏ nhất đã lưu. Nếu không tìm thấy, trả về 0.

Code minh họa:

import math # Cần để sử dụng math.inf

def min_subarray_len(target, nums):
    """
    Tìm chiều dài nhỏ nhất của đoạn con liên tục có tổng >= target.
    Sử dụng kỹ thuật Sliding window.
    """
    n = len(nums)
    # Khởi tạo chiều dài nhỏ nhất là vô cùng (hoặc một số rất lớn)
    min_length = math.inf
    # Tổng của cửa sổ hiện tại
    current_sum = 0
    # Con trỏ trái của cửa sổ
    left = 0

    # right pointer duyệt qua toàn bộ mảng để mở rộng cửa sổ
    for right in range(n):
        # Mở rộng cửa sổ: Thêm phần tử mới ở bên phải vào tổng
        current_sum += nums[right]

        # Khi nào cửa sổ hiện tại thỏa mãn điều kiện (tổng >= target)?
        # Chúng ta cố gắng thu hẹp từ bên trái để tìm chiều dài nhỏ nhất
        while current_sum >= target:
            # Cập nhật chiều dài nhỏ nhất tìm được
            # Chiều dài cửa sổ hiện tại là (right - left + 1)
            min_length = min(min_length, right - left + 1)

            # Thu hẹp cửa sổ: Bớt phần tử ở bên trái ra khỏi tổng
            # và di chuyển con trỏ trái
            current_sum -= nums[left]
            left += 1

    # Nếu min_length vẫn là vô cùng, nghĩa là không tìm thấy đoạn con nào thỏa mãn
    # Trả về 0, ngược lại trả về min_length
    return min_length if min_length != math.inf else 0

# Ví dụ sử dụng
target1 = 7
nums1 = [2, 3, 1, 2, 4, 3]
print(f"Mảng: {nums1}, Target: {target1}")
print(f"Chiều dài nhỏ nhất của đoạn con có tổng >= {target1}: {min_subarray_len(target1, nums1)}") # Output: 2 ([4, 3])

target2 = 4
nums2 = [1, 4, 4]
print(f"Mảng: {nums2}, Target: {target2}")
print(f"Chiều dài nhỏ nhất của đoạn con có tổng >= {target2}: {min_subarray_len(target2, nums2)}") # Output: 1 ([4])

target3 = 11
nums3 = [1, 1, 1, 1, 1, 1, 1, 1]
print(f"Mảng: {nums3}, Target: {target3}")
print(f"Chiều dài nhỏ nhất của đoạn con có tổng >= {target3}: {min_subarray_len(target3, nums3)}") # Output: 0 (Không có)

Giải thích Code:

min_length được khởi tạo với math.inf (một giá trị rất lớn) để bất kỳ chiều dài hợp lệ nào tìm thấy đều nhỏ hơn nó.
current_sum theo dõi tổng các phần tử trong cửa sổ [left, right].
Vòng lặp for right in range(n): mở rộng cửa sổ bằng cách thêm nums[right] vào current_sum.
Vòng lặp while current_sum >= target: là trái tim của logic thu hẹp. Chỉ khi tổng của cửa sổ đạt hoặc vượt target, chúng ta mới xem xét nó như một ứng viên (cập nhật min_length) và sau đó cố gắng thu hẹp nó từ trái (bằng cách trừ nums[left] và tăng left) để xem liệu có thể tìm được một đoạn con ngắn hơn mà vẫn thỏa mãn điều kiện tổng hay không. Vòng lặp while này sẽ chạy nhiều lần liên tiếp nếu cần thiết (ví dụ: nếu cửa sổ rất dài và tổng lớn hơn target nhiều lần).
left và right di chuyển tiến về phía trước, mỗi phần tử được thêm vào và có thể bị xóa khỏi current_sum tối đa một lần. Do đó, độ phức tạp là O(n).
Cuối cùng, chúng ta kiểm tra xem min_length có còn là math.inf không để xác định xem có tìm thấy đoạn con nào thỏa mãn hay không.

Tại Sao Kỹ Thuật Sliding Window Mạnh Mẽ?

Sự mạnh mẽ của Sliding window nằm ở chỗ nó biến đổi nhiều bài toán O(n^2) trên các đoạn con/chuỗi con liên tục thành các giải thuật O(n). Điều này đạt được bằng cách:

Tái sử dụng tính toán: Thay vì tính toán lại từ đầu cho mỗi đoạn con, nó chỉ cập nhật kết quả khi cửa sổ trượt.
Tránh lặp không cần thiết: Nó không xem xét tất cả các đoạn con một cách riêng biệt, mà chỉ xem xét các trạng thái của cửa sổ khi nó di chuyển qua dữ liệu.

Kỹ thuật này đặc biệt hữu ích trong các bài toán liên quan đến:

Tìm kiếm đoạn con/chuỗi con thỏa mãn một điều kiện (tổng, trung bình, chứa/không chứa ký tự, v.v.).
Tìm đoạn con/chuỗi con ngắn nhất hoặc dài nhất thỏa mãn một điều kiện.
Các bài toán trên mảng hoặc chuỗi yêu cầu kiểm tra một "phạm vi" liên tục.

Nắm vững kỹ thuật Sliding window sẽ mở ra cánh cửa để giải quyết nhiều bài toán lập trình thi đấu và phỏng vấn một cách hiệu quả. Hãy luyện tập thêm các bài toán sử dụng kỹ thuật này để thành thạo nó nhé!

Comments

There are no comments at the moment.