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.
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":
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.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.