Kiểm tra chuỗi con palindrome chẵn trong C++

Cho chuỗi chỉ chứa chữ cái thường. Kiểm tra xem chuỗi có chứa **ít nhất một chuỗi con (substring) là palindrome và có độ dài chẵn** hay không.

Quan sát quan trọng

Một palindrome độ dài chẵn **nhỏ nhất** là độ dài 2 (ví dụ: "aa", "bb", "cc").

=> **Chuỗi chứa palindrome chẵn <=> Chuỗi chứa 2 ký tự liên tiếp giống nhau.**

Chứng minh: Nếu có palindrome chẵn dài hơn (vd: "abba"), thì tại tâm nó bắt buộc có cặp ký tự giống nhau ("bb").

Phương pháp giải O(N)

Chỉ cần duyệt chuỗi một lần, kiểm tra s[i] == s[i+1]. Nếu có -> Trả về True.

Chương trình C++

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

bool hasEvenPalindrome(const string& s) {
    for (size_t i = 0; i + 1 < s.length(); i++) {
        if (s[i] == s[i+1]) return true;
    }
    return false;
}

int main() {
    vector<string> tests = {"afternoon", "hello", "world", "abba", "abc", "a"};
    for (auto &t : tests) {
        cout << "\"" << t << "\" -> " << (hasEvenPalindrome(t) ? "Co (True)" : "Khong (False)") << endl;
    }
    return 0;
}

Đầu ra

"afternoon" -> Co (True)   (chua "oo")
"hello" -> Co (True)       (chua "ll")
"world" -> Khong (False)
"abba" -> Co (True)        (chua "bb")
"abc" -> Khong (False)
"a" -> Khong (False)