Các tiền tố có nhiều 'a' hơn 'b' trong C++

Trong bài toán này, chúng ta được cho chuỗi str chỉ chứa a và b và một số nguyên N sao cho một chuỗi được tạo bằng cách nối str n lần. Nhiệm vụ của chúng ta là in tổng số chuỗi con mà số lượng a nhiều hơn số lượng b.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: aab 2
Đầu ra: 9
Giải thích: chuỗi tạo ra là aabaab.
Chuỗi con có count(a) > count(b) :
'a' , 'aa', 'aab', 'aaba', 'aabaa', 'aabaab', 'aba', 'baa', 'abaa'.

Để giải quyết bài toán này, chúng ta sẽ phải kiểm tra xem chuỗi có chứa các tập con tiền tố yêu cầu không. Ở đây, chúng ta sẽ kiểm tra chuỗi str chứ không phải phiên bản đầy đủ. Ở đây, chúng ta sẽ kiểm tra chuỗi dựa trên tiền tố và số lần xuất hiện của a và b.

Chương trình này sẽ minh họa triển khai giải pháp của chúng ta:

Ví dụ

#include <iostream>
#include <string.h>
using namespace std;
int prefixCount(string str, int n){
    int a = 0, b = 0, count = 0;
    int i = 0;
    int len = str.size();
    for (i = 0; i < len; i++) {
        if (str[i] == 'a')
            a++;
        if (str[i] == 'b')
            b++;
        if (a > b) {
            count++;
        }
    }
    if (count == 0 || n == 1) {
        cout<<count;
        return 0;
    }
    if (count == len || a - b == 0) {
        cout<<(count*n);
        return 0;
    }
    int n2 = n - 1, count2 = 0;
    while (n2 != 0) {
        for (i = 0; i < len; i++) {
            if (str[i] == 'a')
                a++;
            if (str[i] == 'b')
                b++;
            if (a > b)
                count2++;
        }
        count += count2;
        n2--;
        if (count2 == 0)
            break;
        if (count2 == len) {
            count += (n2 * count2);
            break;
        }
        count2 = 0;
    }
    return count;
}
int main() {
    string str = "aba";
    int N = 2;
    cout<<"Chuỗi được tạo bằng cách sử dụng '"<<str<<"' "<<N<<" lần có ";
    cout<<prefixCount(str, N)<<" chuỗi con với số lượng a lớn hơn số lượng b";
    return 0;
}

Kết quả

Chuỗi được tạo bằng cách sử dụng 'aba' 2 lần có 5 chuỗi con với số lượng a lớn hơn số lượng b