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

Trong bài toán này, chúng ta được cung cấp 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 ra bằng cách thêm str n lần. Nhiệm vụ của chúng ta là in ra tổng số chuỗi con trong đó số a nhiều hơn số b.

Hãy lấy một ví dụ để hiểu vấn đề

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’.

Để giải quyết vấ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ố bắt buộc hay không. Ở đây, chúng tôi sẽ kiểm tra chuỗi str không phải là phiên bản đầy đủ. Ở đây, w 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ẽ hiển thị việc triển khai giải pháp của chúng tôi

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<<"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;
}

Đầu ra

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