Minimum Changes to Make K Semi-palindromes - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2911. Minimum Changes to Make K Semi-palindromes
Hard
50 Points
Two Pointers
String
Dynamic Programming
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:
Consider the string "abcabc":
Examples
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.
2911. Minimum Changes to Make K Semi-palindromes
Hard
50 Points
Two Pointers
String
Dynamic Programming
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:
Consider the string "abcabc":
Examples
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.