สมมติว่าเรามีสตริง เราต้องหาจำนวนตำแหน่งที่สมดุลในสตริงนั้นโดยที่ส่วนซ้ายและขวาของสตริงมีอักขระเหมือนกัน ความถี่ของตัวอักษรไม่สำคัญ ดังนั้น หากสตริงคือ “ABAABA” จำนวนตำแหน่งสมดุลคือ 3 ตำแหน่งเหล่านี้คือ AB|AABA, ABA|ABA, ABAA|BA
เพื่อแก้ปัญหานี้ เราจะปฏิบัติตามแนวทางที่มีประสิทธิภาพ หลังจากผ่านสตริง เรารู้สึกว่าถูกต้อง[] โดยนับจำนวนอักขระทั้งหมด จากนั้นข้ามสตริงจากซ้ายไปขวา สำหรับอักขระทุกตัว เราเพิ่มจำนวนไปทางซ้าย[] และลดจำนวนไปทางขวา สำหรับจุดใด ๆ ที่กำลังข้ามไป ถ้าอักขระทั้งหมดที่มีค่าไม่เป็นศูนย์ทางด้านซ้ายมีค่าที่ไม่ใช่ศูนย์ทางด้านขวา และในทางกลับกันก็เป็นจริงเช่นกัน แล้วเพิ่มผลลัพธ์
ตัวอย่าง
#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
