Chuỗi con cân bằng (hay còn gọi là chuỗi con xen kẽ X-Y với số lượng bằng nhau) là một bài toán phổ biến trong lập trình, đặc biệt hữu ích trong phân tích mẫu, xử lý dữ liệu và tối ưu thuật toán. Dưới đây là cách triển khai bài toán này bằng cả Python và VBA.

1. Bài toán: Tìm chuỗi con dài nhất có số lượng ký tự X và Y bằng nhau

Yêu cầu: Cho một chuỗi chỉ chứa các ký tự 'X' và 'Y'. Hãy tìm độ dài lớn nhất của một chuỗi con liên tiếp sao cho số lượng 'X' và 'Y' trong chuỗi đó bằng nhau.

Ví dụ đầu vào: "XYXXXYYYX"
Kết quả mong đợi: 8

1-1. Giải pháp bằng Python

class MaxBalancedSubstring:
    def find_max_length(self, text):
        max_len = 0
        prefix_diff = [0] * len(text)
        seen_diff = {}
        
        # Khởi tạo giá trị đầu tiên
        if text[0] == 'X':
            prefix_diff[0] = 1
            seen_diff[1] = 0
        else:
            prefix_diff[0] = -1
            seen_diff[-1] = 0
        
        # Duyệt từng ký tự từ vị trí thứ hai
        for i in range(1, len(text)):
            diff = 1 if text[i] == 'X' else -1
            prefix_diff[i] = prefix_diff[i-1] + diff
            
            # Nếu tổng chênh lệch bằng 0 → từ đầu đến vị trí i cân bằng
            if prefix_diff[i] == 0:
                max_len = i + 1
                continue
                
            # Nếu đã gặp chênh lệch này trước → tính khoảng cách
            if prefix_diff[i] in seen_diff:
                current_span = i - seen_diff[prefix_diff[i]]
                max_len = max(max_len, current_span)
            else:
                seen_diff[prefix_diff[i]] = i
                
        return max_len

# Test chương trình
if __name__ == "__main__":
    input_str = "XYXXXYYYX"
    solver = MaxBalancedSubstring()
    print(f"Chuỗi đầu vào: {input_str}")
    print(f"Độ dài chuỗi con cân bằng dài nhất: {solver.find_max_length(input_str)}")

1-2. Giải pháp bằng VBA

Function FindLongestBalancedSubstr(inputStr As String) As Integer
    Dim maxLength As Integer
    Dim prefixDiff() As Integer
    Dim dict As Object
    Dim i As Integer
    Dim delta As Integer
    Dim key As Variant
    
    maxLength = 0
    ReDim prefixDiff(1 To Len(inputStr))
    Set dict = CreateObject("Scripting.Dictionary")
    
    ' Khởi tạo phần tử đầu tiên
    If Left(inputStr, 1) = "X" Then
        prefixDiff(1) = 1
        dict.Add 1, 1
    Else
        prefixDiff(1) = -1
        dict.Add -1, 1
    End If
    
    ' Duyệt từ ký tự thứ 2 đến cuối
    For i = 2 To Len(inputStr)
        delta = IIf(Mid(inputStr, i, 1) = "X", 1, -1)
        prefixDiff(i) = prefixDiff(i - 1) + delta
        
        If prefixDiff(i) = 0 Then
            maxLength = i
        ElseIf dict.Exists(prefixDiff(i)) Then
            Dim span As Integer
            span = i - dict(prefixDiff(i))
            maxLength = Application.WorksheetFunction.Max(maxLength, span)
        Else
            dict.Add prefixDiff(i), i
        End If
    Next i
    
    FindLongestBalancedSubstr = maxLength
End Function

Sub RunTest()
    Dim testString As String
    Dim result As Integer
    
    testString = "XYXXXYYYX"
    result = FindLongestBalancedSubstr(testString)
    Debug.Print "Độ dài chuỗi con cân bằng lớn nhất: " & result
End Sub

Lưu ý: Nhập mã VBA vào trình soạn thảo VBA (Alt+F11), chạy macro RunTest() để xem kết quả tại cửa sổ Immediate (Ctrl+G).

2. Ứng dụng thực tế

• Phân tích chuỗi DNA/RNA: Phát hiện đoạn gen có sự cân bằng giữa các cặp nucleotide.
• Xử lý tín hiệu: Nhận diện chu kỳ lặp lại trong tín hiệu điện.
• Thực thi giao thức mạng: Kiểm tra cấu trúc dữ liệu yêu cầu cân bằng ký tự.
• Mã hóa và giải mã: Đảm bảo sự cân bằng trong quá trình mã hóa.
• Phân tích văn bản: Phát hiện mẫu lặp hoặc cấu trúc đối xứng.
• Nén dữ liệu: Tìm mẫu trùng lặp để tối ưu hóa nén.

3. Tài liệu tham khảo

• Python-VBA 500 ví dụ - Bài 20 đến 24