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