Độ dài chuỗi cân bằng tối đa sau khi hoán đổi và xóa ký tự trong C++

Chúng ta được cho một chuỗi chỉ chứa các ký tự (,),{,},[,]. Mục tiêu là tìm độ dài tối đa của chuỗi như vậy sao cho nó trở thành cân bằng bằng cách hoán đổi các ký tự liền kề hoặc xóa một ký tự. Chúng ta sẽ làm điều này bằng cách so sánh các ký tự liền kề, nếu chúng là đối lập của nhau thì có thể hoán đổi. ( }{,)(,][ có thể hoán đổi, trong khi {{,)),[[,}},)),]] không thể hoán đổi).

Cũng nếu một ký tự không có cặp khớp, thì nó cũng có thể bị xóa. ( "{{}]][()", ở đây { đầu tiên có thể bị xóa và độ dài chuỗi cân bằng trở thành 4).

Ví dụ

Đầu vào

str[] = "{{{}}{]]][()" độ dài 12

Đầu ra

Độ dài chuỗi cân bằng tối đa: 8

Giải thích − str[0] và str[1] không thể hoán đổi, xóa str[0] = "{{}}{]]][()" str[1] và str[2] gốc không thể hoán đổi, xóa str[1] = "{}}{]]][()" {} đã cân bằng }{ có thể hoán đổi, xóa 2 ]] tiếp theo, hoán đổi ][ và () cũng cân bằng. Chuỗi cuối cùng là {}{}[](). Độ dài là 8.

Đầu vào

str[] = "(((((()" độ dài 7

Đầu ra

str[] = "(((((()" độ dài 7

Giải thích − Chỉ str[5] và str[6] cân bằng, xóa tất cả. Chuỗi cuối cùng (). Độ dài là 2.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng ký tự str[] lưu chuỗi gốc. Số nguyên Length lưu độ dài chuỗi.
• Hàm maxBalancedStr(char str[], int len) nhận chuỗi và độ dài làm tham số, trả về độ dài tối đa của chuỗi cân bằng.
• Biến count lưu độ dài chuỗi như vậy, khởi tạo 0.
• Duyệt chuỗi từ ký tự đầu tiên và kiểm tra nếu ký tự liền kề có thể hoán đổi để cả hai cân bằng. Hoặc nếu chúng đã cân bằng, tăng count lên 2.
• Làm điều này cho các cặp như (),)( và {},}{ và [],[], tăng i cũng nếu cặp như vậy tồn tại, để chuyển sang ký tự tiếp theo.
• Cuối cùng count lưu độ dài chuỗi cân bằng.
• Trả về count làm kết quả.

Ví dụ mã nguồn

// C++ implementation of the approach
#include <bits/stdc++.h> 
using namespace std; 

// Hàm trả về độ dài chuỗi con cân bằng dài nhất
int maxBalancedStr(char str[20], int len) { 
    int count = 0; 
    // Duyệt chuỗi
    for (int i = 0; i < len; i++) { 
        // Kiểm tra loại ngoặc và tăng count cho nó
        if ((str[i] == '(' && str[i + 1] == ')') || (str[i] == ')' && str[i + 1] == '(')) { // có thể hoán đổi
            count += 2; 
            ++i; 
        } else if ((str[i] == '{' && str[i + 1] == '}') || (str[i] == '}' && str[i + 1] == '{')) { // có thể hoán đổi
            count += 2; 
            ++i; 
        } else if ((str[i] == '[' && str[i + 1] == ']') || (str[i] == ']' && str[i + 1] == '[')) { // có thể hoán đổi
            count += 2; 
            ++i; 
        } 
    } 
    return count; 
} 

// Mã điều khiển
int main() { 
    char str[] = ")(]](("; 
    int length = 7; 
    cout << maxBalancedStr(str, length); 
    return 0; 
}

Kết quả

4