# 1278. Palindrome Partitioning III

You are given a string `s`

containing lowercase letters and an integer `k`

. You need to :

- First, change some characters of
`s`

to other lowercase English letters. - Then divide
`s`

into`k`

non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

**Example 1:**

**Input:**

s = "abc", k = 2

**Output:**

1

**Explanation:**

You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

**Example 2:**

**Input:**

s = "aabbc", k = 3

**Output:**

0

**Explanation:**

You can split the string into "aa", "bb" and "c", all of them are palindrome.

**Example 3:**

**Input:**

s = "leetcode", k = 8

**Output:**

0

**Constraints:**

`1 <= k <= s.length <= 100`

.`s`

only contains lowercase English letters.

Failed to build the dp during the contest : ( . it was quite close

class Solution { public int palindromePartition(String s, int k) { if (k == s.length()){ return 0; } int[][] dp = new int[s.length()+1][k+1]; for (int i = 0; i <= s.length(); i++) for (int j = 0; j <= k; j++) dp[i][j] = s.length(); dp[0][0] = 0; for (int i = 0; i < s.length(); i ++){ for (int j = 0; j < k; j ++){ for (int len = 1; i + len <= s.length(); len++) { int cost = 0; for (int a = i, b = i + len - 1; a < b; a++, b--){ if (s.charAt(a) != s.charAt(b)){ cost ++; } } dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost); } } } return dp[s.length()][k]; } }

Few things to point out:

- I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp

## 0 Comments