在C ++中查找字符串中的平衡位置数

假设我们有一个字符串。我们必须从该字符串的左右部分包含相同字符的位置找到该字符串中的平衡位置计数。字符的频率无关紧要。因此，如果字符串为“ ABAABA”，则平衡位置的数目为3。这些位置为AB | AABA，ABA | ABA，ABAA | BA。

为了解决这个问题，我们将遵循一些有效的方法。遍历字符串后，我们首先对所有字符计数感到正确[]。然后从左到右遍历字符串。对于每个字符，我们在left []中增加其计数，并在right中减少计数。对于任何要遍历的点，如果所有左侧具有非零值的字符在右侧也具有非零值，反之亦然。然后增加结果。

示例

#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;
int countBalancePoints(string str) {
   int left[MAX_CHAR] = {0};
   int right[MAX_CHAR] = {0};
   for (int i=0; i<str.length(); i++)
   right[str[i]]++;
   int count = 0;
   for (int i=0; i < str.length() ; i++) {
      left[str[i]]++;
      right[str[i]]--;
      int j;
      for (j=0; j<MAX_CHAR; j++) {
         if ( (left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
         break;
      }
      if (j == MAX_CHAR)
         count++;
   }
   return count;
}
int main() {
   char str[] = "ABAABA";
   cout << "Number of balance points: " << countBalancePoints(str);
}

输出结果

Number of balance points: 3