C++에서 문자열의 균형 위치 수 찾기

문자열이 있다고 가정합니다. 문자열의 왼쪽과 오른쪽 부분에 같은 문자가 포함된 문자열에서 균형 위치 수를 찾아야 합니다. 문자의 빈도는 중요하지 않습니다. 따라서 문자열이 "ABAABA"이면 균형 위치의 수는 3입니다. 이러한 위치는 AB|AABA, ABA|ABA, ABAA|BA입니다.

이를 해결하기 위해 우리는 몇 가지 효율적인 접근 방식을 따를 것입니다. 문자열을 순회한 후 우리는 먼저 모든 문자의 수로 옳다고 느낀다[]. 그런 다음 문자열을 왼쪽에서 오른쪽으로 이동합니다. 모든 문자에 대해 왼쪽[]에서 카운트를 증가시키고 오른쪽에서 카운트를 감소시킵니다. 트래버스되는 모든 지점에 대해 왼쪽에 0이 아닌 값이 있는 모든 문자의 오른쪽에도 0이 아닌 값이 있고 그 반대의 경우도 마찬가지입니다. 그런 다음 결과를 증가시키십시오.

예

#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