Phá vỡ chuỗi đối xứng (Palindrome) trong C++

Cho một chuỗi đối xứng (palindrome), ta cần thay đổi chính xác một ký tự bằng một chữ cái thường bất kỳ để chuỗi kết quả trở thành chuỗi không đối xứng và có thứ tự từ điển (lexicographically) nhỏ nhất có thể. Nếu không làm được, trả về chuỗi rỗng.

Ví dụ

Input: "abccba" → Output: "aaccba"

Thuật toán

1. Nếu độ dài chuỗi = 1 → trả về chuỗi rỗng (không thể phá vỡ).
2. Duyệt từ đầu và cuối chuỗi về phía giữa (con trỏ i từ 0, j từ n-1).
3. Tại mỗi cặp ký tự đối xứng:
   • Nếu s[i] != 'a', thay s[i] = 'a' và trả về ngay (đây là thay đổi nhỏ nhất có thể).
   • Tăng i, giảm j.
4. Nếu duyệt hết mà toàn bộ là 'a' (chuỗi toàn 'a'), thay ký tự cuối cùng thành 'b'.
5. Trả về chuỗi kết quả.

Ví dụ code C++

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

class Solution {
public:
    string breakPalindrome(string s) {
        if (s.size() == 1) return "";
        
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (s[i] != 'a') {
                s[i] = 'a';
                return s;
            }
            i++; j--;
        }
        
        // Trường hợp chuỗi toàn 'a' (vd: "aaa") -> thay cuối thành 'b'
        s[s.size() - 1] = 'b';
        return s;
    }
};

int main() {
    Solution ob;
    cout << ob.breakPalindrome("abccba"); // Output: aaccba
    return 0;
}

Đầu vào / Đầu ra

Input:  "abccba"
Output: aaccba

Giải thích

Với "abccba", cặp đầu tiên khác 'a' là s[1] = 'b'. Thay thành 'a' ta được "aaccba" - chuỗi không đối xứng và nhỏ nhất theo từ điển.