การทำลายพาลินโดรมใน C++

สมมติว่าเรามีสตริงที่เป็นพาลินโดรม (อ่านจากหน้าหลังได้เหมือนกัน) เราต้องเปลี่ยนตัวอักษรเพียงตัวเดียวให้เป็นตัวอักษรภาษาอังกฤษพิมพ์เล็ก ใดๆ เพื่อให้สตริงที่ได้เป็นสตริงที่เล็กที่สุดในลำดับเล็กซิโครกราฟิก (lexicographically smallest) และไม่ใช่พาลินโดรม หากไม่สามารถทำได้ ให้คืนค่าสตริงว่าง ตัวอย่างเช่น อินพุต "abccba" จะได้เอาต์พุต "aaccba"

ขั้นตอนการแก้ปัญหา

1. changed := false
2. ถ้าความยาวสตริงเท่ากับ 1 ให้คืนค่าสตริงว่าง
3. i := 0 และ j := ความยาวสตริง - 1
4. วนลูป while i < j:
   • ถ้า s[i] ไม่ใช่ 'a' ให้ตั้งค่า s[i] = 'a' และคืนค่า s
   • เพิ่ม i ลง 1 และลด j ลง 1
5. ตั้งค่า s[ความยาวสตริง - 1] = 'b'
6. คืนค่า s

ตัวอย่างโค้ด (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--;
        }
        
        s[s.size() - 1] = 'b';
        return s;
    }
};

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

อินพุต

"abccba"

เอาต์พุต

aaccba