C++ || Recursion || Memoization || DP
Approach\n Describe your approach to solving the problem. \n1. Find all possible combinations of consecutive K groups.\n2. From each group find the number of ch
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Find all possible combinations of consecutive K groups.\n2. From each group find the number of characters that can be changed to make this whole group palindrome.\n3. Track the minimum answer from all possible combinations.\n\n# Complexity\n- Time complexity: $$O(n*n*k)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n*k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code (Memoization)\n```\nclass Solution {\nprivate:\n    int numberOfChangesRequired(int i, int j, string &s)\n    {\n        int count = 0;\n        while(i < j)\n        {\n            if(s[i] != s[j])\n            {\n                ++count;\n            }\n            ++i;\n            --j;\n        }\n        return count;\n    }\nprivate:\n    int memoization(int index, int size, string &s, int k, vector<vector<int>>&dp)\n    {\n        if(k == 1)\n        {\n            return numberOfChangesRequired(index, size - 1, s);\n        }\n        if(dp[index][k] != -1)\n        {\n            return dp[index][k];\n        }\n        int mini = INT_MAX;\n        for(int i = index; i <= (size - k); ++i)\n        {\n            int count = numberOfChangesRequired(index, i, s) + memoization(i + 1, size, s, k - 1, dp);\n            mini = min(mini, count);\n        }\n        return dp[index][k] = mini;\n    }\npublic:\n    int palindromePartition(string s, int k) {\n        int size = s.size();\n        vector<vector<int>>dp(size, vector<int>(k + 1, -1));\n        return memoization(0, size, s, k, dp);\n    }\n};\n```
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']