จำนวนการลบน้อยที่สุดเพื่อทำให้สตริงเป็นพาลินโดรมด้วย C++

ข้อความโจทย์

กำหนดสตริงขนาด 'n' งานคือลบจำนวนตัวอักษรน้อยที่สุดเพื่อทำให้สตริงเป็นพาลินโดรม (Palindrome)

ถ้าสตริงที่กำหนดคือ "abcda" เราสามารถลบตัวอักษรใดก็ได้ 2 ตัว ยกเว้นตัวแรกและตัวสุดท้าย เพื่อทำให้มันเป็นพาลินโดรม

• ถ้าลบตัวอักษร 'b' และ 'c' แล้ว "ada" เป็นพาลินโดรม
• ถ้าลบตัวอักษร 'c' และ 'd' แล้ว "aba" เป็นพาลินโดรม
• ถ้าลบตัวอักษร 'b' และ 'd' แล้ว "aca" เป็นพาลินโดรม

อัลกอริทึม

1. หาลำดับย่อยพาลินโดรมที่ยาวที่สุด (Longest Palindromic Subsequence) ของสตริงที่กำหนด ให้เรียกว่า "lpsSize"
2. ตัวอักษรขั้นต่ำที่ต้องลบ = (ความยาวของสตริง - lpsSize)

ตัวอย่างโค้ด

#include <iostream>
#include <algorithm>
using namespace std;

int lps(string s, int i, int j) {
    if (i == j) {
        return 1;
    }
    if (s[i] == s[j] && i + 1 == j) {
        return 2;
    }
    if (s[i] == s[j]) {
        return lps(s, i + 1, j - 1) + 2;
    }
    return max(lps(s, i, j - 1), lps(s, i + 1, j));
}

int minDeletion(string s) {
    int n = s.size();
    int lpsSize = lps(s, 0, n);
    return (n - lpsSize);
}

int main() {
    cout << "Minimum characters to be deleted = " << minDeletion("abcda") << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum characters to be deleted = 2