565. Splitting Into k Palindromes

Split the string into exactly k non-empty consecutive pieces. Each piece must be made into a palindrome by CHANGING characters, one change per character. Print the fewest changes in total.

abc, k = 2 -> 1 a | bc, changing one of b or c aabbc, k = 3 -> 0 aa | bb | c, all already palindromes

## Two tables, each simple

cost[i][j] = changes needed to make s[i..j] a palindrome dp[i][g] = fewest changes for the first i characters split into g pieces

The interval table supplies the piece costs and the partition table consumes them. Neither half is hard; keeping them separate is what makes the whole thing manageable.

## The piece cost

Walking from both ends inward, each mismatched PAIR costs exactly one change, since changing either character fixes the pair:

cost = number of positions t with s[i+t] != s[j-t], over t < (j-i+1)/2

A middle character in an odd-length piece has no partner and costs nothing, which is why the loop stops when the two pointers meet.

Counting mismatched CHARACTERS rather than pairs doubles every cost. ab with k = 1 answers 1 and is the test: two characters mismatch, one change fixes them.

## The partition

dp[0][0] = 0 dp[i][g] = min over p of dp[p][g-1] + cost[p][i-1]

with p running from g-1 to i-1, so every piece is non-empty.

## The bounds on p

The first p characters must fill g-1 non-empty pieces, so p >= g-1. The last piece must be non-empty, so p <= i-1.

Getting the lower bound wrong lets a piece be empty and the answer comes out too small. That is the same bound as problem 561, and the same check applies: with k equal to the string length, every piece is one character and the answer must be 0.

leetcode with k = 8 answers 0 and is that test.

## Two boundaries worth pairing

ab with k = 1 answers 1 and with k = 2 answers 0. Same string, and more pieces can only help, because a single character is always a palindrome.

More generally the answer is non-increasing in k, which is a cheap sanity check on any implementation.

## An input worth tracing

abcde with k = 2 answers 2. The splits are a|bcde costing 2, ab|cde costing 1 + 1, abc|de costing 1 + 1, and abcd|e costing 2. Every split costs 2, so the answer does not depend on the choice, which makes it a poor test of the split logic and a good test of the cost function.

## Cost

Time O(n^2) to build the costs incrementally, or O(n^3) directly, plus O(n^2 k) for the partition. Space O(n^2).

Constraints - `1 ≤ k ≤ length of the string ≤ 100` - the string contains only lowercase letters