C++ এ প্যালিনড্রোম পার্টিশনিং III

ধরুন আমাদের একটি স্ট্রিং s আছে যাতে ছোট হাতের অক্ষর এবং একটি পূর্ণসংখ্যা k রয়েছে। আমাদের কিছু বৈশিষ্ট্য বজায় রাখতে হবে। এগুলো হল -

• প্রথমে, আমাদেরকে s-এর কিছু অক্ষর (যদি প্রয়োজন হয়) অন্য ছোট হাতের ইংরেজি অক্ষরে পরিবর্তন করতে হবে।
• তারপর স্ট্রিং s কে k সাবস্ট্রিং এ বিভক্ত করুন যাতে প্রতিটি সাবস্ট্রিং একটি প্যালিনড্রোম হয়।

স্ট্রিং ভাগ করার জন্য আমাদের ন্যূনতম সংখ্যক অক্ষর খুঁজে বের করতে হবে যা আমাদের পরিবর্তন করতে হবে।

সুতরাং যদি স্ট্রিংটি "ababbc" এবং k =2 এর মত হয়, তাহলে উত্তর হবে 1, কারণ এটিকে দুটি প্যালিনড্রোম স্ট্রিংয়ে বিভক্ত করতে আমাদের একটি অক্ষর পরিবর্তন করতে হবে। তাই যদি আমরা c থেকে b, অথবা দ্বিতীয় শেষ b থেকে c পরিবর্তন করি, তাহলে আমরা একটি প্যালিনড্রোম পেতে পারি যেমন হয় "bbb" বা "cbc", এবং আরেকটি প্যালিনড্রোম "aba"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের একটি অ্যারে মেমো সংজ্ঞায়িত করুন:105 x 105।
• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি s, idx, k, একটি 2D অ্যারে> dp,
• যদি idx s এর আকারের সমান হয়, তাহলে −
  • ক 0 হলে ফেরত দিন তারপর 0 অন্যথায় 1000
• যদি মেমো[idx][k] -1 এর সমান না হয়, তাহলে −
  • রিটার্ন মেমো[idx][k]
• যদি k <=0 হয়, তাহলে −
  • রিটার্ন ইনফ
• উত্তর :=inf
• আরম্ভ করার জন্য i :=idx, যখন i
• উত্তর :=সর্বনিম্ন উত্তর এবং 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