นับพาลินโดรมพิเศษ (Special Palindromes) ในสตริงใน C++

เราได้รับสตริง str เป้าหมายคือนับทุก substring ที่เป็น "พาลินโดรมพิเศษ" และมีความยาวมากกว่า 1 พาลินโดรมพิเศษคือสตริงที่:

• มีตัวอักษรเหมือนกันทุกตัว (เช่น "aaa")
• หรือมีเพียงตัวกลางที่ต่างออกไป (เช่น "aba", "aabaa")

ตัวอย่าง

อินพุต: str = "abccdcdf"

เอาต์พุต: 3

คำอธิบาย: Substring ที่เป็นพาลินโดรมพิเศษ: "cc", "cdc", "dcd"

อินพุต: str = "baabaab"

เอาต์พุต: 4

คำอธิบาย: "aa", "aabaa", "aba", "aa"

แนวทางการแก้ปัญหา

ใช้อัลกอริทึมที่นับกลุ่มตัวอักษรติดกัน และตรวจสอบรูปแบบที่ตัวกลางต่างออกไป โดยใช้ array เก็บความยาวกลุ่มตัวอักษรติดกัน

การนำไปใช้ (Implementation)

#include <bits/stdc++.h>
using namespace std;

int count_palindromes(string str, int len) {
    int count = 0, i = 0;
    int arr[len] = {0};
    
    while (i < len) {
        int total = 1;
        int j = i + 1;
        while (str[i] == str[j] && j < len) {
            total++;
            j++;
        }
        count += (total * (total + 1) / 2);
        arr[i] = total;
        i = j;
    }
    
    for (int j = 1; j < len; j++) {
        if (str[j] == str[j - 1]) {
            arr[j] = arr[j - 1];
        }
        int temp = str[j - 1];
        if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)) {
            count += min(arr[j-1], arr[j+1]);
        }
    }
    
    count = count - len; // ลบพาลินโดรมความยาว 1 ออก
    return count;
}

int main() {
    string str = "bcbaba";
    int len = str.length();
    cout << "Count of special palindromes in a String are: " << count_palindromes(str, len);
    return 0;
}

เอาต์พุต

Count of special palindromes in a String are: 3