सी++ में पलिंड्रोम पार्टिशनिंग III

मान लीजिए कि हमारे पास एक स्ट्रिंग s है जिसमें लोअरकेस अक्षर और एक पूर्णांक k है। हमें कुछ संपत्तियों को बनाए रखना होगा। ये हैं -

• सबसे पहले, हमें s के कुछ अक्षरों (यदि आवश्यक हो) को अन्य लोअरकेस अंग्रेजी अक्षरों में बदलना होगा।
• फिर स्ट्रिंग s को k सबस्ट्रिंग में इस तरह विभाजित करें कि प्रत्येक सबस्ट्रिंग एक पैलिंड्रोम हो।

स्ट्रिंग को विभाजित करने के लिए हमें कम से कम वर्णों को बदलना होगा जिन्हें हमें बदलने की आवश्यकता है।

तो अगर स्ट्रिंग "एबैब" और के =2 की तरह है, तो उत्तर 1 होगा, क्योंकि हमें इसे दो पैलिंड्रोम स्ट्रिंग्स में विभाजित करने के लिए एक वर्ण को बदलना होगा। इसलिए यदि हम c को b में बदलते हैं, या दूसरे अंतिम b को c में बदलते हैं, तो हम एक पैलिंड्रोम प्राप्त कर सकते हैं जैसे या तो "bbb" या "cbc", और दूसरा पैलिंड्रोम "aba" है।

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

• आकार का एक सरणी मेमो परिभाषित करें:105 x 105।
• एक फ़ंक्शन को हल करें () को परिभाषित करें, इसमें s, idx, k, एक 2D सरणी> dp,
लगेगा।
• यदि idx, s के आकार के समान है, तो −
  • वापसी तब करें जब k 0 हो तो 0 अन्यथा 1000
• यदि मेमो[idx][k] -1 के बराबर नहीं है, तो −
  • वापसी ज्ञापन[idx][k]
• यदि k <=0, तो −
  • वापसी की जानकारी
• उत्तर:=जानकारी
• इनिशियलाइज़ i :=idx के लिए, जब i
• Ans :=न्यूनतम उत्तर और dp[idx][i] + फ़ंक्शन को हल करें (s, i + 1, k-1, dp)

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int memo[105][105];
   lli solve(string s, int idx, int k, vector < vector <int> > &dp){
      if(idx == s.size()) {
         return k == 0? 0 : 1000;
      }
      if(memo[idx][k] != -1) return memo[idx][k];
      if(k <= 0)return INT_MAX;
      lli ans = INT_MAX;
      for(int i = idx; i < s.size(); i++){
         ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
      }
      return memo[idx][k] = ans;
   }
   int palindromePartition(string s, int k) {
      int n = s.size();
      memset(memo, -1, sizeof(memo));
      vector < vector <int> > dp(n, vector <int>(n));
      for(int l =2; l <= n; l++){
         for(int i = 0, j = l - 1; j <n; j++, i++){
            if(l==2){
               dp[i][j] = !(s[i] == s[j]);
            }else{
               dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
            }
         }
      }
      return solve(s, 0, k, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.palindromePartition("ababbc", 2));
}

“ababbc”

1