Задача: 1278. Palindrome Partitioning III
Сложность: hard

Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку.

Пример:

Input: s = "abc", k = 2
Output: 1

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром.

2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений.

3⃣Верните минимальное количество изменений, найденное во втором шаге.

😎 Решение:

class Solution {
    func minChangesToMakePalindrome(_ s: String, _ k: Int) -> Int {
        let n = s.count
        let sArray = Array(s)
        
        func minChangeToPalindrome(_ i: Int, _ j: Int) -> Int {
            var changes = 0
            var i = i
            var j = j
            while i < j {
                if sArray[i] != sArray[j] {
                    changes += 1
                }
                i += 1
                j -= 1
            }
            return changes
        }
        
        var dp1 = Array(repeating: Array(repeating: 0, count: n), count: n)
        for length in 1...n {
            for i in 0...(n - length) {
                let j = i + length - 1
                dp1[i][j] = minChangeToPalindrome(i, j)
            }
        }

        var dp2 = Array(repeating: Array(repeating: Int.max, count: k + 1), count: n + 1)
        dp2[0][0] = 0

        for i in 1...n {
            for kk in 1...k {
                for j in 0..<i {
                    dp2[i][kk] = min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1])
                }
            }
        }

        return dp2[n][k]
    }
}

Ставь 👍 и забирай 📚 Базу знаний