Đếm số phép toán để làm cho chuỗi nhị phân không chứa "ab" trong C++

Cho một chuỗi có thể chứa mẫu "ab". Nhiệm vụ: đếm số phép toán cần thiết để xóa toàn bộ "ab" khỏi chuỗi. Mỗi phép toán thay thế "ab" bằng "bba".

Ví dụ

Đầu vào − str = "ababaa"

Đầu ra − 4

Giải thích:

"ababaa" → thay "ab"→"bba" (lần 1) → "bbaabaa"
→ thay "ab"→"bba" (lần 2) → "bbabbaaa"
→ thay "ab"→"bba" (lần 3) → "bbabbbaaa"
→ thay "ab"→"bba" (lần 4) → "bbabbbbaaa" (không còn "ab")

Đầu vào − str = "abaa"

Đầu ra − 1

Giải thích − "abaa" → "bbaaa" (1 lần), không còn "ab".

Phương pháp giải

Duyệt chuỗi từ phải sang trái. Giữ biến total đếm số 'b' đã gặp. Khi gặp 'a', số phép toán tăng thêm total, và total = total * 2 (vì mỗi 'a' sẽ nhân đôi số 'b' phía sau sau khi thay thế).

• Hàm operations_ab_free(string str, int len).
• Khởi tạo count = 0, total = 0.
• Duyệt i từ 0 đến len-1 (từ phải sang trái qua arr[len-i-1]):
  • Nếu ký tự là 'a': count += total; total *= 2;
  • Ngược là 'b': total++.
• Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int operations_ab_free(string str, int len) {
    int count = 0;
    int total = 0;
    for (int i = 0; i < len; i++) {
        if (str[len - i - 1] == 'a') {
            count += total;
            total *= 2;
        } else {
            total++;
        }
    }
    return count;
}

int main() {
    string str = "ababaa";
    int length = str.length();
    cout << "Count of operations to make a binary string \"ab\" free are: " << operations_ab_free(str, length) << endl;
    return 0;
}

Đầu ra

Count of operations to make a binary string "ab" free are: 4