1278. Palindrome Partitioning III LeetCode Solution
In this guide, you will get 1278. Palindrome Partitioning III LeetCode Solution with the best time and space complexity. The solution to Palindrome Partitioning III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given a string s containing lowercase letters and an integer k. You need to :
First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.
Return the minimal number of characters that you need to change to divide the string.
Example 1:
Input: s = “abc”, k = 2
Output: 1
Explanation: You can split the string into “ab” and “c”, and change 1 character in “ab” to make it palindrome.
Example 2:
Input: s = “aabbc”, k = 3
Output: 0
Explanation: You can split the string into “aa”, “bb” and “c”, all of them are palindrome.
Example 3:
Input: s = “leetcode”, k = 8
Output: 0
Constraints:
1 <= k <= s.length <= 100.
s only contains lowercase English letters.
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
1278. Palindrome Partitioning III LeetCode Solution in C++
class Solution {
public:
int palindromePartition(string s, int k) {
const int n = s.length();
vector<vector<int>> mem(n + 1, vector<int>(k + 1, n));
// cost[i][j] := the minimum cost to make s[i..j] palindrome
vector<vector<int>> cost(n, vector<int>(n));
for (int d = 1; d < n; ++d)
for (int i = 0, j = d; j < n; ++i, ++j)
cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
return palindromePartition(n, k, cost, mem);
}
private:
// Returns the minimum cost to make k palindromes by s[0..i).
int palindromePartition(int n, int k, const vector<vector<int>>& cost,
vector<vector<int>>& mem) {
if (k == 1)
return cost[0][n - 1];
if (mem[n][k] < n)
return mem[n][k];
// Try all the possible partitions.
for (int i = k - 1; i < n; ++i)
mem[n][k] = min(
mem[n][k], palindromePartition(i, k - 1, cost, mem) + cost[i][n - 1]);
return mem[n][k];
}
}; /* code provided by PROGIEZ */
1278. Palindrome Partitioning III LeetCode Solution in Java
class Solution {
public int palindromePartition(String s, int k) {
final int n = s.length();
int[][] mem = new int[n + 1][k + 1];
// cost[i][j] := the minimum cost to make s[i..j] palindrome
int[][] cost = new int[n][n];
Arrays.stream(mem).forEach(A -> Arrays.fill(A, n));
for (int d = 1; d < n; ++d)
for (int i = 0, j = d; j < n; ++i, ++j)
cost[i][j] = (s.charAt(i) == s.charAt(j) ? 0 : 1) + cost[i + 1][j - 1];
return palindromePartition(n, k, cost, mem);
}
// Returns the minimum cost to make k palindromes by s[0..i).
private int palindromePartition(int n, int k, int[][] cost, int[][] mem) {
if (k == 1)
return cost[0][n - 1];
if (mem[n][k] < n)
return mem[n][k];
// Try all the possible partitions.
for (int i = k - 1; i < n; ++i)
mem[n][k] = Math.min(mem[n][k], //
palindromePartition(i, k - 1, cost, mem) + cost[i][n - 1]);
return mem[n][k];
}
} // code provided by PROGIEZ
1278. Palindrome Partitioning III LeetCode Solution in Python
class Solution {
public:
int palindromePartition(string s, int K) {
const int n = s.length();
// dp[i][k] := the minimum cost to make k palindromes by s[0..i)
vector<vector<int>> dp(n + 1, vector<int>(K + 1, n));
// cost[i][j] := the minimum cost to make s[i..j] palindrome
vector<vector<int>> cost(n, vector<int>(n));
for (int d = 1; d < n; ++d)
for (int i = 0, j = d; j < n; ++i, ++j)
cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
for (int i = 1; i <= n; ++i)
dp[i][1] = cost[0][i - 1];
for (int k = 2; k <= K; ++k)
for (int i = k; i <= n; ++i)
for (int j = k - 1; j < i; ++j)
dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j][i - 1]);
return dp[n][K];
}
}; # code by PROGIEZ
