मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें लोअरकेस अक्षर हैं और एक पूर्णांक k है। हमें कुछ गुणों को बनाए रखना है। ये हैं -
- पहले, हमें s के कुछ वर्णों को (यदि आवश्यक हो) अन्य लोअरकेस अंग्रेजी अक्षरों में बदलना होगा।
- फिर स्ट्रिंग s को k उपस्ट्रिंग में विभाजित करना होगा ताकि प्रत्येक उपस्ट्रिंग एक पालिंड्रोम हो।
हमें स्ट्रिंग को विभाजित करने के लिए बदलने के लिए आवश्यक न्यूनतम वर्णों की संख्या ज्ञात करनी है।
तो यदि स्ट्रिंग "ababbc" जैसी है और k = 2, तो उत्तर 1 होगा, क्योंकि हमें दो पालिंड्रोम स्ट्रिंग में विभाजित करने के लिए एक वर्ण बदलना होगा। तो यदि हम c को b में बदलते हैं, या अंत से दूसरा b को c में, तो हमें एक पालिंड्रोम मिल सकता है जैसे "bbb" या "cbc", और दूसरा पालिंड्रोम "aba" है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- आकार 105 x 105 का एक ऐरे memo परिभाषित करें।
- एक फंक्शन solve() परिभाषित करें, यह s, idx, k, एक 2D ऐरे dp लेगा,
- यदि idx s के आकार के समान है, तो -
- वापस करें जब k 0 हो तो 0 अन्यथा 1000
- यदि memo[idx][k] -1 के बराबर नहीं है, तो -
- memo[idx][k] वापस करें
- यदि k <= 0, तो -
- inf वापस करें
- ans := inf
- i := idx से प्रारंभ करें, जब i < s का आकार, i बढ़ाते हुए, करें -
- ans := ans का न्यूनतम और dp[idx][i] + solve(s, i + 1, k - 1, dp) फंक्शन कॉल करें
- memo[idx][k] = ans वापस करें
- मुख्य विधि से, निम्न करें
- n := s का आकार
- memo को -1 से भरें
- आकार n x n का एक 2D ऐरे dp परिभाषित करें
- l := 2 से प्रारंभ करें, जब l <= n, l बढ़ाते हुए, करें -
- i := 0, j := l - 1 से प्रारंभ करें, जब j < n, j बढ़ाते हुए, i बढ़ाते हुए, करें -
- यदि l 2 के समान है, तो -
- dp[i][j] := true जब s[i] s[j] के समान नहीं है
- अन्यथा
- dp[i][j] := dp[i + 1][j - 1] + 0 जब s[i] s[j] के समान है
- i := 0, j := l - 1 से प्रारंभ करें, जब j < n, j बढ़ाते हुए, i बढ़ाते हुए, करें -
- solve(s, 0, k, 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