2911. Minimum Changes to Make K Semi-palindromes LeetCode Solution
In this guide, you will get 2911. Minimum Changes to Make K Semi-palindromes LeetCode Solution with the best time and space complexity. The solution to Minimum Changes to Make K Semi-palindromes 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.
Problem Statement of Minimum Changes to Make K Semi-palindromes
Given a string s and an integer k, partition s into k substrings such that the letter changes needed to make each substring a semi-palindrome are minimized.
Return the minimum number of letter changes required.
A semi-palindrome is a special type of string that can be divided into palindromes based on a repeating pattern. To check if a string is a semi-palindrome:
Choose a positive divisor d of the string’s length. d can range from 1 up to, but not including, the string’s length. For a string of length 1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.
For a given divisor d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d. Specifically, the first group consists of characters at positions 1, 1 + d, 1 + 2d, and so on; the second group includes characters at positions 2, 2 + d, 2 + 2d, etc.
The string is considered a semi-palindrome if each of these groups forms a palindrome.
Consider the string “abcabc”:
The length of “abcabc” is 6. Valid divisors are 1, 2, and 3.
For d = 1: The entire string “abcabc” forms one group. Not a palindrome.
For d = 2:
Group 1 (positions 1, 3, 5): “acb”
Group 2 (positions 2, 4, 6): “bac”
Neither group forms a palindrome.
For d = 3:
Group 1 (positions 1, 4): “aa”
Group 2 (positions 2, 5): “bb”
Group 3 (positions 3, 6): “cc”
All groups form palindromes. Therefore, “abcabc” is a semi-palindrome.
Example 1:
Input: s = “abcac”, k = 2
Output: 1
Explanation: Divide s into “ab” and “cac”. “cac” is already semi-palindrome. Change “ab” to “aa”, it becomes semi-palindrome with d = 1.
Example 2:
Input: s = “abcdef”, k = 2
Output: 2
Explanation: Divide s into substrings “abc” and “def”. Each needs one change to become semi-palindrome.
Example 3:
Input: s = “aabbaa”, k = 3
Output: 0
Explanation: Divide s into substrings “aa”, “bb” and “aa”. All are already semi-palindromes.
Constraints:
2 <= s.length <= 200
1 <= k <= s.length / 2
s contains only lowercase English letters.
Complexity Analysis
Time Complexity: O(n^2k) = O(n^3)
Space Complexity: O(n^2)
2911. Minimum Changes to Make K Semi-palindromes LeetCode Solution in C++
class Solution {
public:
int minimumChanges(string s, int k) {
const int n = s.length();
// factors[i] := factors of i
const vector<vector<int>> factors = getFactors(n);
// cost[i][j] := changes to make s[i..j] a semi-palindrome
const vector<vector<int>> cost = getCost(s, n, factors);
// dp[i][j] := the minimum changes to split s[i:] into j valid parts
vector<vector<int>> dp(n + 1, vector<int>(k + 1, n));
dp[n][0] = 0;
for (int i = n - 1; i >= 0; --i)
for (int j = 1; j <= k; ++j)
for (int l = i + 1; l < n; ++l)
dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + cost[i][l]);
return dp[0][k];
}
private:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> factors(n + 1);
for (int i = 1; i <= n; ++i)
factors[i].push_back(1);
for (int d = 2; d < n; ++d)
for (int i = d * 2; i <= n; i += d)
factors[i].push_back(d);
return factors;
}
vector<vector<int>> getCost(const string& s, int n,
const vector<vector<int>>& factors) {
vector<vector<int>> cost(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
const int length = j - i + 1;
int minCost = length;
for (const int d : factors[length])
minCost = min(minCost, getCost(s, i, j, d));
cost[i][j] = minCost;
}
return cost;
}
// Returns the cost to make s[i..j] a semi-palindrome of `d`.
int getCost(const string& s, int i, int j, int d) {
int cost = 0;
for (int offset = 0; offset < d; ++offset) {
int l = i + offset;
int r = j - d + 1 + offset;
while (l < r) {
if (s[l] != s[r])
++cost;
l += d;
r -= d;
}
}
return cost;
}
}; /* code provided by PROGIEZ */
2911. Minimum Changes to Make K Semi-palindromes LeetCode Solution in Java
class Solution {
public int minimumChanges(String s, int k) {
final int n = s.length();
// factors[i] := factors of i
List<Integer>[] factors = getFactors(n);
// cost[i][j] := changes to make s[i..j] a semi-palindrome
int[][] cost = getCost(s, n, factors);
// dp[i][j] := the minimum changes to split s[i:] into j valid parts
int[][] dp = new int[n + 1][k + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));
dp[n][0] = 0;
for (int i = n - 1; i >= 0; --i)
for (int j = 1; j <= k; ++j)
for (int l = i + 1; l < n; ++l)
dp[i][j] = Math.min(dp[i][j], dp[l + 1][j - 1] + cost[i][l]);
return dp[0][k];
}
private List<Integer>[] getFactors(int n) {
List<Integer>[] factors = new List[n + 1];
for (int i = 1; i <= n; ++i)
factors[i] = new ArrayList<>(List.of(1));
for (int d = 2; d < n; ++d)
for (int i = d * 2; i <= n; i += d)
factors[i].add(d);
return factors;
}
private int[][] getCost(final String s, int n, List<Integer>[] factors) {
int[][] cost = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
final int length = j - i + 1;
int minCost = length;
for (final int d : factors[length])
minCost = Math.min(minCost, getCost(s, i, j, d));
cost[i][j] = minCost;
}
return cost;
}
// Returns the cost to make s[i..j] a semi-palindrome of `d`.
private int getCost(final String s, int i, int j, int d) {
int cost = 0;
for (int offset = 0; offset < d; ++offset) {
int l = i + offset;
int r = j - d + 1 + offset;
while (l < r) {
if (s.charAt(l) != s.charAt(r))
++cost;
l += d;
r -= d;
}
}
return cost;
}
} // code provided by PROGIEZ
2911. Minimum Changes to Make K Semi-palindromes LeetCode Solution in Python
class Solution:
def minimumChanges(self, s: str, k: int) -> int:
n = len(s)
# factors[i] := factors of i
factors = self._getFactors(n)
# cost[i][j] := changes to make s[i..j] a semi-palindrome
cost = self._getCost(s, n, factors)
# dp[i][j] := the minimum changes to split s[i:] into j valid parts
dp = [[n] * (k + 1) for _ in range(n + 1)]
dp[n][0] = 0
for i in range(n - 1, -1, -1):
for j in range(1, k + 1):
for l in range(i + 1, n):
dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + cost[i][l])
return dp[0][k]
def _getFactors(self, n: int) -> list[list[int]]:
factors = [[1] for _ in range(n + 1)]
for d in range(2, n):
for i in range(d * 2, n + 1, d):
factors[i].append(d)
return factors
def _getCost(self, s: str, n: int, factors: list[list[int]]) -> list[list[int]]:
cost = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
length = j - i + 1
minCost = length
for d in factors[length]:
minCost = min(minCost, self._getCostD(s, i, j, d))
cost[i][j] = minCost
return cost
def _getCostD(self, s: str, i: int, j: int, d: int) -> int:
"""Returns the cost to make s[i..j] a semi-palindrome of `d`."""
cost = 0
for offset in range(d):
l = i + offset
r = j - d + 1 + offset
while l < r:
if s[l] != s[r]:
cost += 1
l += d
r -= d
return cost # code by PROGIEZ
