LeetCode Entry
2911. Minimum Changes to Make K Semi-palindromes
Min changes to split into k semi-palindromes (step of divisors of length)
2911. Minimum Changes to Make K Semi-palindromes hard substack youtube
https://dmitrysamoylenko.com/leetcode/

Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1545
Problem TLDR
Min changes to split into k semi-palindromes (step of divisors of length)
Intuition
Dp to try every possible split i…end, cache by (i, k). Check semi-palindrome diff with brute force.
Approach
- single letter is not a semi-palindrome
Complexity
-
Time complexity: \(O(nk)\)
-
Space complexity: \(O(nk)\)
Code
fun minimumChanges(s: String, k: Int): Int {
val m = HashMap<Int, Int>()
fun f(i: Int, k: Int): Int = if (i == s.length && k == 0) 0 else if (i >= s.length || k == 0) 999
else m.getOrPut(i * 999 + k) {
(i + 1..<s.length).minOfOrNull { x ->
f(x + 1, k - 1) + m.getOrPut(-i * 999 - x) {
val L = x - i + 1
(1..<L).filter { L % it == 0 }.minOf { d ->
(0..<d).sumOf { j ->
val g = (i + j..x step d).map { s[it] }
(0..<g.size / 2).count { g[it] != g[g.lastIndex - it] }
}
}
}
} ?: 999
}
return f(0, k)
}
Comments