# 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