Python 3 || 9 lines, recursion  || T/S: 86% / 31%
Here\'s the plan:\n1. If the string is the length k, no are changes required, and we return 0.\n\n2. If k == 1, we return the score of that string.\n3. Other wi
Here\'s the plan:\n1. If the string is the length `k`, no are changes required, and we return 0.\n\n2. If `k == 1`, we return the score of that string.\n3. Other wise, we iteratively halve the string. We treat the left half as the left-most substring, and recurse the right half.\n4. We determine the optimum answer from this iteration.\n                                      \n \n```\nclass Solution:\n    @lru_cache(None)\n    def palindromePartition(self, s: str, k: int) -> int:\n\n        n, ans = len(s), inf\n\n        if n == k: return 0                         # <-- 1)\n\n        if k == 1:                                  # <-- 2)\n            return sum(s[i] != s[~i] for i in range(n//2))\n    \n    for i in range(n - k + 1):                      # <-- 3)\n            sm = (self.palindromePartition(s[:i+1],     1) +\n                  self.palindromePartition(s[i+1:], k - 1))\n\n            if sm < ans: ans = sm                   # <-- 4)\n\n        return ans     \n```\n[https://leetcode.com/problems/palindrome-partitioning-iii/submissions/1361795649/](https://leetcode.com/problems/palindrome-partitioning-iii/submissions/1361795649/)
['Python3']