Prefix ที่มี a มากกว่า b ใน C++

ในปัญหานี้ เราได้รับสตริง str ที่มีแค่ a และ b และจำนวนเต็ม N ที่ทำให้สตริงถูกสร้างโดยการนำ str มาต่อกัน n ครั้ง งานของเราคือพิมพ์จำนวนรวมของ substring ที่จำนวน a มากกว่าจำนวน b

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา

Input: aab 2
Output: 9
Explanation: created string is aabaab.
Substrings with count(a) > count(b) :
'a' , 'aa', 'aab', 'aaba', 'aabaa', 'aabaab', 'aba', 'baa', 'abaa'.

ในการแก้ปัญหานี้ เราจะต้องตรวจสอบว่าสตริงมี subset prefix ที่ต้องการอยู่หรือไม่ ที่นี่ เราจะตรวจสอบสตริง str ไม่ใช่ full version ที่นี่ w จะตรวจสอบสตริงโดยอิงจาก prefix และจำนวนครั้งที่ a และ b เกิดขึ้น

โปรแกรมนี้จะแสดงการนำวิธีแก้ปัญหาของเราไปใช้

ตัวอย่างโค้ด

#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<<"The string created by using '"<<str<<"' "<<N<<" times has ";
    cout<<prefixCount(str, N)<<" substring with count of a greater than count of b";
    return 0;
}

ผลลัพธ์

The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b