<p>You are given a string <code>s</code> containing lowercase letters and an integer <code>k</code>. You need to :</p>

<ul>
	<li>First, change some characters of <code>s</code> to other lowercase English letters.</li>
	<li>Then divide <code>s</code> into <code>k</code> non-empty disjoint substrings such that each substring is a palindrome.</li>
</ul>

<p>Return <em>the minimal number of characters that you need to change to divide the string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;, k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;ab&quot; and &quot;c&quot;, and change 1 character in &quot;ab&quot; to make it palindrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabbc&quot;, k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;aa&quot;, &quot;bb&quot; and &quot;c&quot;, all of them are palindrome.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, k = 8
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 100</code>.</li>
	<li><code>s</code> only contains lowercase English letters.</li>
</ul>

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def reqToChange(st):
            start=0
            end=len(st)-1
            cnt=0
            while(start<end):
                if(st[start]!=st[end]):
                    cnt+=1
                start+=1
                end-=1
            return cnt
        def check(ind, cntP):
            if(ind>=len(s)):
               # print(cntP)
                if(cntP==k):
                    return 0
                return float("inf")
            if((ind,cntP) in cache):
                return cache[(ind,cntP)]
            ans=float("inf")
            for nextInd in range(ind+1,len(s)+1):
                st=s[ind:nextInd]
                req=reqToChange(st)
                ans=min(ans,req+check(nextInd,cntP+1))
            cache[(ind,cntP)]=ans
            return ans
        cache={}
        ans=check(0,0)
        # if(ans==float("inf")):
        #     return 0
        return ans

        
18000