C++ में वैलिड पैलिंड्रोम III

मान लीजिए हमारे पास एक स्ट्रिंग s और एक अन्य संख्या k है; हमें जांचना होगा कि दी गई स्ट्रिंग K-पैलिंड्रोम है या नहीं।

एक स्ट्रिंग को K-पैलिंड्रोम कहा जाता है यदि इसे अधिकतम k कैरेक्टर्स को हटाकर पैलिंड्रोम में बदला जा सकता है।

तो, यदि इनपुट s = "abcdeca", k = 2 है, तो आउटपुट true होगा क्योंकि 'b' और 'e' कैरेक्टर्स को हटाकर, यह पैलिंड्रोम बन जाएगी।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

एक फ़ंक्शन lcs() परिभाषित करें, जो s, t लेगा,
n := s का आकार
s से पहले एक ब्लैंक स्पेस जोड़ें
t से पहले एक ब्लैंक स्पेस जोड़ें
आकार (n + 1) x (n + 1) का एक 2D ऐरे dp परिभाषित करें
i := 1 से शुरू करें, जब i <= n, अपडेट करें (i को 1 से बढ़ाएं), करें:
- j := 1 से शुरू करें, जब j <= n, अपडेट करें (j को 1 से बढ़ाएं), करें:
  - dp[i, j] := dp[i - 1, j] और dp[i, j - 1] का अधिकतम
  - यदि s[i], t[j] के समान है, तो:
    - dp[i, j] := dp[i, j] और 1 + dp[i - 1, j - 1] का अधिकतम
dp[n, n] लौटाएं
मुख्य मेथड से निम्नलिखित करें:
यदि s का आकार नहीं है, तो:
- true लौटाएं
x := ब्लैंक स्पेस
i := s के आकार से शुरू करें, जब i >= 0, अपडेट करें (i को 1 से घटाएं), करें:
- x := x + s[i]
s का आकार लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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

class Solution {
public:
    int lcs(string s, string t) {
        int n = s.size();
        s = " " + s;
        t = " " + t;
        vector> dp(n + 1, vector(n + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (s[i] == t[j])
                    dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
        }
        return dp[n][n];
    }

    bool isValidPalindrome(string s, int k) {
        if (!s.size())
            return true;
        string x = "";
        for (int i = s.size() - 1; i >= 0; i--)
            x += s[i];
        return s.size() - lcs(s, x) <= k;
    }
};

int main() {
    Solution ob;
    cout << (ob.isValidPalindrome("abcdeca", 2));
}

इनपुट

"abcdeca", 2