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