255. Palindrome Partitioning III
š LeetCode Problem: 1278. Palindrome Partitioning III
š Difficulty: Hard
š·ļø Topics: String, Dynamic Programming, DP - MCM (Matrix Chain Multiplication)
Problem Statement
You are given a string s containing lowercase letters and an integer k. You need to:
- Partition the string into
knon-empty disjoint substrings such that each substring is a palindrome after changing at most a few characters.
Return the minimum number of characters that you need to change to divide the string into k substrings such that each substring is a palindrome.
Example 1:
Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 thing 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 consists of lowercase English letters only.
š§ Starting From Absolute Zero
Understanding The Problem Step By Step
Let me work through Example 1 VERY slowly:
s = "abc", k = 2
GOAL: Split into EXACTLY 2 parts where each part is a palindrome
(We can CHANGE characters to make palindromes!)
Let me try different ways to split into 2 parts:
WAY 1: Split as "a" | "bc"
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Part 1: "a"
Is "a" palindrome? YES! ā
Changes needed: 0
Part 2: "bc"
Is "bc" palindrome? NO!
Forward: bc
Backward: cb
To make palindrome: change 'b' to 'c' OR 'c' to 'b'
Changes needed: 1
Total changes: 0 + 1 = 1 ā
WAY 2: Split as "ab" | "c"
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Part 1: "ab"
Is "ab" palindrome? NO!
Forward: ab
Backward: ba
To make palindrome: change 'a' to 'b' OR 'b' to 'a'
Changes needed: 1
Part 2: "c"
Is "c" palindrome? YES! ā
Changes needed: 0
Total changes: 1 + 0 = 1 ā
MINIMUM = 1 ā
Answer: 1
The Key Difference From Problem 253
Problem 253 (Palindrome Partitioning II):
- Split into palindrome parts
- CANNOT change characters
- Minimize NUMBER OF CUTS
Problem 255 (Palindrome Partitioning III):
- Split into EXACTLY k parts
- CAN change characters
- Minimize NUMBER OF CHANGES
Big differences:
1. Must use exactly k parts (not minimize parts!)
2. Can change characters to make palindromes!
3. Minimize changes (not cuts!)
Completely different problem! š
Understanding "Changes to Make Palindrome"
Let me understand how to count changes:
String: "abc"
To make it palindrome:
Position 0 vs Position 2: 'a' vs 'c'
Don't match! Need to change one of them
Changes: 1
Position 1: 'b' (middle, no need to match)
Total changes needed: 1
Another example: "abcd"
To make it palindrome:
Position 0 vs Position 3: 'a' vs 'd' ā need 1 change
Position 1 vs Position 2: 'b' vs 'c' ā need 1 change
Total changes needed: 2
Algorithm:
Compare s[i] with s[j] (from ends)
If different: need 1 change
Count all such pairs! š
š¤ Building Understanding - What's The Challenge?
Observation 1: We Must Use Exactly k Parts
Example: s = "aabbc", k = 3
We MUST split into exactly 3 parts!
Can't split into 2 parts (even if that needs 0 changes)
Can't split into 4 parts (even if that's easier)
MUST be 3!
This is a CONSTRAINT, not an optimization! š
Observation 2: Different Splits Give Different Costs
s = "abc", k = 2
Split 1: "a" | "bc"
Cost: 0 + 1 = 1
Split 2: "ab" | "c"
Cost: 1 + 0 = 1
Split 3... wait, we can only split 3-character string
into 2 parts in 2 ways!
But for longer strings, MANY ways to split!
Example: s = "abcd", k = 2
Split 1: "a" | "bcd"
Cost for "a": 0
Cost for "bcd": ?
Split 2: "ab" | "cd"
Cost for "ab": 1 (make it "aa" or "bb")
Cost for "cd": 1 (make it "cc" or "dd")
Total: 2
Split 3: "abc" | "d"
Cost for "abc": 1
Cost for "d": 0
Total: 1
Different splits ā different costs!
Need to find MINIMUM! š
Observation 3: Each Part Has a Cost
The cost of a substring depends on:
- Its characters
- How many need to change to make it palindrome
This cost is INDEPENDENT of:
- Where we split
- What other parts look like
Example: Substring "abc"
Cost to make palindrome: 1
This is same whether it's:
- The first part of a split
- The middle part
- The last part
We can PRECOMPUTE these costs! š
šÆ Approach 1: Brute Force - Try All Ways
The Naive Idea
To split string into k parts:
- Try every possible position for first split
- Recursively split the rest into k-1 parts
- Calculate total cost
- Track minimum
Example: s = "abcd", k = 2
Try first split after position 0: "a" | "bcd"
Cost("a") + solve("bcd", k=1)
Try first split after position 1: "ab" | "cd"
Cost("ab") + solve("cd", k=1)
Try first split after position 2: "abc" | "d"
Cost("abc") + solve("d", k=1)
Take minimum! ā
How To Calculate Cost of Making Palindrome
private int costToMakePalindrome(String s, int start, int end) {
int changes = 0;
// Compare from both ends
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
changes++; // Need to change one of them
}
start++;
end--;
}
return changes;
}
Example trace:
costToMakePalindrome("abc", 0, 2):
start=0, end=2: 'a' != 'c'? YES ā changes=1
start=1, end=1: start not < end, stop
Return 1 ā
costToMakePalindrome("aa", 0, 1):
start=0, end=1: 'a' != 'a'? NO
start=1, end=0: start not < end, stop
Return 0 ā
Complete Brute Force Implementation
class Solution {
private int minChanges = Integer.MAX_VALUE;
public int palindromePartition(String s, int k) {
solve(s, 0, k, 0);
return minChanges;
}
// pos: current position in string
// partsLeft: how many parts still need to create
// changes: changes made so far
private void solve(String s, int pos, int partsLeft, int changes) {
// Base case: reached end of string
if (pos == s.length()) {
if (partsLeft == 0) {
// Used all parts!
minChanges = Math.min(minChanges, changes);
}
return;
}
// Base case: no parts left but string not finished
if (partsLeft == 0) {
return; // Invalid, need more parts!
}
// Try taking substrings of different lengths for next part
for (int end = pos; end < s.length(); end++) {
// Take s[pos...end] as one part
int cost = costToMakePalindrome(s, pos, end);
// Recursively partition the rest
solve(s, end + 1, partsLeft - 1, changes + cost);
}
}
private int costToMakePalindrome(String s, int start, int end) {
int changes = 0;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
changes++;
}
start++;
end--;
}
return changes;
}
}
Complete Trace Example
s = "abc", k = 2
solve(pos=0, partsLeft=2, changes=0)
ā
āā end=0: Take "a" (pos 0 to 0)
ā cost = costToMakePalindrome("abc", 0, 0) = 0
ā solve(pos=1, partsLeft=1, changes=0)
ā ā
ā āā end=1: Take "b" (pos 1 to 1)
ā ā cost = 0
ā ā solve(pos=2, partsLeft=0, changes=0)
ā ā ā
ā ā āā end=2: partsLeft=0, can't take more
ā ā Invalid! Return
ā ā
ā āā end=2: Take "bc" (pos 1 to 2)
ā cost = costToMakePalindrome("abc", 1, 2)
ā start=1, end=2: 'b' != 'c'? YES ā cost=1
ā solve(pos=3, partsLeft=0, changes=1)
ā
ā pos == length AND partsLeft == 0 ā
ā minChanges = min(INF, 1) = 1
ā
āā end=1: Take "ab" (pos 0 to 1)
ā cost = costToMakePalindrome("abc", 0, 1)
ā start=0, end=1: 'a' != 'b'? YES ā cost=1
ā solve(pos=2, partsLeft=1, changes=1)
ā ā
ā āā end=2: Take "c" (pos 2 to 2)
ā cost = 0
ā solve(pos=3, partsLeft=0, changes=1)
ā
ā pos == length AND partsLeft == 0 ā
ā minChanges = min(1, 1) = 1
ā
āā end=2: Take "abc" (pos 0 to 2)
cost = costToMakePalindrome("abc", 0, 2) = 1
solve(pos=3, partsLeft=1, changes=1)
pos == length BUT partsLeft == 1 ā
Still need 1 more part! Invalid!
Final: minChanges = 1 ā
Why Brute Force Is Too Slow
TIME COMPLEXITY:
Number of ways to split string of length n into k parts:
This is a combinatorial problem!
For each position, we decide: is this a split point?
We need exactly k-1 split points among n-1 positions
Ways = C(n-1, k-1) = (n-1)! / ((k-1)! Ć (n-k)!)
For each way:
- Calculate cost for each of k parts: O(k Ć n)
Overall: O(C(n-1, k-1) Ć k Ć n) ā
For n=100, k=50:
C(99, 49) is HUGE! ā
SPACE: O(n) recursion stack
Need optimization! ā DP!
š” Discovering The DP Pattern
Observation 1: Overlapping Subproblems
In the recursion tree:
solve(pos=2, partsLeft=1) appears multiple times:
- After taking "ab" from position 0
- After taking "a" then "b" separately
- Other paths...
We're solving same subproblem repeatedly!
This is OVERLAPPING SUBPROBLEMS! š
Observation 2: Optimal Substructure
The minimum changes for s[0...n] with k parts depends on:
- Taking some prefix as first part
- Optimally partitioning the rest into k-1 parts
If we know the optimal solution for suffix with k-1 parts,
we can build optimal solution for whole string with k parts!
This is OPTIMAL SUBSTRUCTURE! š
ā Use DYNAMIC PROGRAMMING! ā
Observation 3: Cost Calculation Is Repeated
We calculate costToMakePalindrome for same substrings many times!
Example: cost for "bc" calculated whenever we consider it as a part
Can we PRECOMPUTE all costs?
YES! For all possible substrings! š
This will speed up our DP! ā
šÆ Approach 2: DP with Precomputation
Step 1: Precompute All Palindrome Costs
For every substring s[i...j]:
Precompute: cost to make it a palindrome
Store in: cost[i][j]
Why?
In DP, we'll query this many times
Precomputing makes each query O(1)! š
Implementation:
// Build cost table
int n = s.length();
int[][] cost = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int start = 0; start <= n - len; start++) {
int end = start + len - 1;
// Calculate cost for s[start...end]
int changes = 0;
int left = start, right = end;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
changes++;
}
left++;
right--;
}
cost[start][end] = changes;
}
}
Example for s = "abc":
LENGTH 1:
cost[0][0] = "a" ā 0 changes
cost[1][1] = "b" ā 0 changes
cost[2][2] = "c" ā 0 changes
LENGTH 2:
cost[0][1] = "ab"
'a' != 'b'? YES ā 1 change
cost[1][2] = "bc"
'b' != 'c'? YES ā 1 change
LENGTH 3:
cost[0][2] = "abc"
'a' != 'c'? YES ā 1 change
(middle 'b' doesn't need comparison)
cost table:
end=0 end=1 end=2
start=0 0 1 1
start=1 - 0 1
start=2 - - 0
Step 2: Define DP State
What information do we need?
dp[i][j] = minimum changes to partition s[0...i] into j parts
Why these dimensions?
i: how much of string we've processed (0 to n-1)
j: how many parts we've used (1 to k)
Base case:
dp[i][1] = cost[0][i] (make entire prefix one palindrome)
Recurrence:
dp[i][j] = min over all previous positions p:
dp[p][j-1] + cost[p+1][i]
Meaning: Use j-1 parts for s[0...p],
Use 1 part for s[p+1...i]
Complete DP Implementation
class Solution {
public int palindromePartition(String s, int k) {
int n = s.length();
// STEP 1: Precompute cost table
int[][] cost = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int start = 0; start <= n - len; start++) {
int end = start + len - 1;
int changes = 0;
int left = start, right = end;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
changes++;
}
left++;
right--;
}
cost[start][end] = changes;
}
}
// STEP 2: DP for minimum changes
int[][] dp = new int[n][k + 1];
// Initialize with infinity
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
// Base case: partition s[0...i] into 1 part
for (int i = 0; i < n; i++) {
dp[i][1] = cost[0][i];
}
// Fill DP table
for (int i = 0; i < n; i++) {
for (int parts = 2; parts <= k; parts++) {
// Try all previous positions for last split
for (int prev = parts - 2; prev < i; prev++) {
// Use 'parts-1' for s[0...prev]
// Use 1 part for s[prev+1...i]
if (dp[prev][parts - 1] != Integer.MAX_VALUE) {
dp[i][parts] = Math.min(dp[i][parts],
dp[prev][parts - 1] + cost[prev + 1][i]);
}
}
}
}
return dp[n - 1][k];
}
}
Understanding The Recurrence
dp[i][j] = minimum changes to partition s[0...i] into j parts
To compute dp[i][j], we try every possible position for the LAST split:
For each position prev (before i):
- Use j-1 parts for s[0...prev]
- Use 1 part for s[prev+1...i]
Total cost = dp[prev][j-1] + cost[prev+1][i]
Take minimum over all valid prev! š
Example: dp[3][2] for s="abcd"
Try prev=0: dp[0][1] + cost[1][3]
(1 part for "a") + (1 part for "bcd")
Try prev=1: dp[1][1] + cost[2][3]
(1 part for "ab") + (1 part for "cd")
Try prev=2: dp[2][1] + cost[3][3]
(1 part for "abc") + (1 part for "d")
Take minimum! ā
š Complete Example Trace
Example: s = "aabbc", k = 3
STEP 1: Build cost table
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
String: "aabbc" (indices 0,1,2,3,4)
Length 1: All single chars ā cost 0
Length 2:
cost[0][1] = "aa": 'a'=='a'? YES ā 0
cost[1][2] = "ab": 'a'=='b'? NO ā 1
cost[2][3] = "bb": 'b'=='b'? YES ā 0
cost[3][4] = "bc": 'b'=='c'? NO ā 1
Length 3:
cost[0][2] = "aab": 'a'=='b'? NO ā 1
cost[1][3] = "abb": 'a'=='b'? NO ā 1
cost[2][4] = "bbc": 'b'=='c'? NO ā 1
Length 4:
cost[0][3] = "aabb": 'a'=='b' (1), 'a'=='b' (1) ā 2
cost[1][4] = "abbc": 'a'=='c' (1), 'b'=='b' (0) ā 1
Length 5:
cost[0][4] = "aabbc": 'a'=='c' (1), 'a'=='b' (1) ā 2
cost table:
0 1 2 3 4
0 0 0 1 2 2
1 - 0 1 1 1
2 - - 0 0 1
3 - - - 0 1
4 - - - - 0
STEP 2: Build DP table
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
dp[i][j] = min changes for s[0...i] using j parts
Base case (j=1): Make whole prefix 1 palindrome
dp[0][1] = cost[0][0] = 0
dp[1][1] = cost[0][1] = 0
dp[2][1] = cost[0][2] = 1
dp[3][1] = cost[0][3] = 2
dp[4][1] = cost[0][4] = 2
Compute dp[i][2]:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
dp[1][2]: Split "aa" into 2 parts
prev=0: dp[0][1] + cost[1][1] = 0 + 0 = 0 ā
dp[2][2]: Split "aab" into 2 parts
prev=0: dp[0][1] + cost[1][2] = 0 + 1 = 1
prev=1: dp[1][1] + cost[2][2] = 0 + 0 = 0 ā
dp[3][2]: Split "aabb" into 2 parts
prev=0: dp[0][1] + cost[1][3] = 0 + 1 = 1
prev=1: dp[1][1] + cost[2][3] = 0 + 0 = 0 ā
prev=2: dp[2][1] + cost[3][3] = 1 + 0 = 1
dp[4][2]: Split "aabbc" into 2 parts
prev=0: dp[0][1] + cost[1][4] = 0 + 1 = 1
prev=1: dp[1][1] + cost[2][4] = 0 + 1 = 1
prev=2: dp[2][1] + cost[3][4] = 1 + 1 = 2
prev=3: dp[3][1] + cost[4][4] = 2 + 0 = 2
Minimum: 1
Compute dp[i][3]:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
dp[2][3]: Split "aab" into 3 parts
prev=1: dp[1][2] + cost[2][2] = 0 + 0 = 0 ā
dp[3][3]: Split "aabb" into 3 parts
prev=1: dp[1][2] + cost[2][3] = 0 + 0 = 0 ā
prev=2: dp[2][2] + cost[3][3] = 0 + 0 = 0 ā
dp[4][3]: Split "aabbc" into 3 parts ā ANSWER!
prev=1: dp[1][2] + cost[2][4] = 0 + 1 = 1
prev=2: dp[2][2] + cost[3][4] = 0 + 1 = 1
prev=3: dp[3][2] + cost[4][4] = 0 + 0 = 0 ā
Minimum: 0 ā
Answer: dp[4][3] = 0
The partition: "aa" | "bb" | "c"
All already palindromes! ā
š Complexity Analysis
PRECOMPUTATION:
cost table:
Two nested loops: O(nĀ²)
For each cell: O(n) to calculate cost
Total: O(nĀ³)
Wait, can we optimize this?
Yes! We process by length
For each substring: O(length) work
Total across all substrings: O(nĀ²) cells Ć O(n) work = O(nĀ³)
Actually, it's tighter:
Sum of all substring lengths ā O(nĀ³)
But typically written as O(nĀ³)
DP TABLE:
Build dp[i][j]:
Outer loops: O(n Ć k)
Inner loop: O(n) positions to try
Total: O(nĀ² Ć k)
OVERALL:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
TIME: O(nĀ³ + nĀ²k) = O(nĀ³) when k ā¤ n
For n=100, k=50:
100Ā³ + 100Ā²Ć50 = 1,000,000 + 500,000 = 1.5M ops ā
Fast enough! ā
SPACE: O(nĀ² + nk) = O(nĀ²)
cost table: O(nĀ²)
dp table: O(nk)
Total: O(nĀ²)
š Key Insights
The Complete Journey
CRAWL (Understanding):
ā What does the problem ask?
ā Manual example worked through
ā Difference from Problem 253
ā How to count changes for palindrome
WALK (Discovery):
ā Brute force approach (try all splits)
ā Overlapping subproblems found
ā Optimal substructure identified
ā Need for precomputation realized
RUN (Mastery):
ā Precompute cost table
ā Define DP state clearly
ā Build DP table systematically
ā Complete example traced
ā Optimal solution achieved!
Pattern Recognition
This problem is PARTITION DP with twist:
Standard Partition DP:
- Minimize cuts/cost
- Variable number of parts
This Problem:
- FIXED number of parts (k)
- Minimize changes
- Need 2D DP (position Ć parts)
Recognition:
"Split into exactly k parts" ā 2D DP with parts dimension
"Minimize cost" ā Try all split positions
"Cost per part" ā Precompute costs
Common Mistakes
ā Forgetting to precompute costs
Recalculating costs in DP ā O(nā“) time!
ā Wrong DP dimensions
Using dp[i] instead of dp[i][j]
Need parts dimension!
ā Wrong base case
dp[i][1] should be cost[0][i]
Not cost[i][i]!
ā Loop bounds
prev must be at least parts-2
(Need parts-1 items before last part)
š» Complete Working Code
class Solution {
public int palindromePartition(String s, int k) {
int n = s.length();
// Precompute cost table
int[][] cost = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int start = 0; start <= n - len; start++) {
int end = start + len - 1;
int changes = 0;
int left = start, right = end;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
changes++;
}
left++;
right--;
}
cost[start][end] = changes;
}
}
// DP table
int[][] dp = new int[n][k + 1];
// Initialize with infinity
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
// Base case
for (int i = 0; i < n; i++) {
dp[i][1] = cost[0][i];
}
// Fill DP table
for (int i = 0; i < n; i++) {
for (int parts = 2; parts <= k; parts++) {
for (int prev = parts - 2; prev < i; prev++) {
if (dp[prev][parts - 1] != Integer.MAX_VALUE) {
dp[i][parts] = Math.min(dp[i][parts],
dp[prev][parts - 1] + cost[prev + 1][i]);
}
}
}
}
return dp[n - 1][k];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.palindromePartition("abc", 2)); // 1
System.out.println(sol.palindromePartition("aabbc", 3)); // 0
System.out.println(sol.palindromePartition("leetcode", 8)); // 0
}
}
š Quick Revision
šÆ Core Algorithm
1. Precompute cost[i][j] = changes to make s[i...j] palindrome
2. Define dp[i][j] = min changes for s[0...i] using j parts
3. Base: dp[i][1] = cost[0][i]
4. Recurrence: dp[i][j] = min(dp[prev][j-1] + cost[prev+1][i])
5. Answer: dp[n-1][k]
š Quick Implementation
public class Solution {
int minCost = Integer.MAX_VALUE;
public int palindromePartition(String s, int k) {
minCost = Integer.MAX_VALUE;
// recursive(s, k, 0, 0);
// return minCost;
return bottomUp(s, k);
}
public int bottomUp(String s, int k) {
int n = s.length();
// STEP 1: Precompute cost table
int[][] cost = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int start = 0; start <= n - len; start++) {
int end = start + len - 1;
int changes = 0;
int left = start, right = end;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
changes++;
}
left++;
right--;
}
cost[start][end] = changes;
}
}
// STEP 2: DP for minimum changes
int[][] dp = new int[n][k + 1];
// Initialize with infinity
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
// Base case: partition s[0...i] into 1 part
for (int i = 0; i < n; i++) {
dp[i][1] = cost[0][i];
}
// Fill DP table
for (int i = 0; i < n; i++) {
for (int parts = 2; parts <= k; parts++) {
// Try all previous positions for last split
for (int prev = parts - 2; prev < i; prev++) {
// Use 'parts-1' for s[0...prev]
// Use 1 part for s[prev+1...i]
if (dp[prev][parts - 1] != Integer.MAX_VALUE) {
dp[i][parts] = Math.min(dp[i][parts],
dp[prev][parts - 1] + cost[prev + 1][i]);
}
}
}
}
return dp[n - 1][k];
}
private void recursive(String s, int k, int begin, int cost) {
// step 3 - base case 1
if (begin == s.length()) {
// we divided into k substrings
if (k == 0) {
minCost = Math.min(minCost, cost);
}
return;
}
// step 3 - base case 2
if (k == 0) {
return;
}
// step 1 - lets take "abcd", k = 2, begin = 0 and cost = 0 initially
// cost() is a function that returns the min cost
// required to convert to a palindrome
// a | bcd
// c = cost("a") => min cost req to convert "a" to a palindrome
// recursive("bcd", 1, 1, cost + c) => solve for remaining
// ab | cd
// c = cost("ab")
// recursive("cd", 1, 2, cost + c)
// abc | d
// c = cost("abc")
// recursive("d", 1, 3, cost + c)
for (int end = begin; end < s.length(); end++) {
int changes = changes(s, begin, end);
// step 2 - solve for the remaining string
recursive(s, k - 1, end + 1, cost + changes);
}
}
private int changes(String s, int begin, int end) {
int changes = 0;
while (begin < end) {
if (s.charAt(begin) != s.charAt(end)) {
changes++;
}
begin++;
end--;
}
return changes;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.palindromePartition("abc", 2) == 1);
System.out.println(s.palindromePartition("abcd", 2) == 1);
System.out.println(s.palindromePartition("aabbc", 3) == 0);
System.out.println(s.palindromePartition("leetcode", 8) == 0);
}
}
ā” Complexity
TIME: O(nĀ³)
SPACE: O(nĀ²)
š Congratulations!
You've mastered: - ā 2D DP with fixed parts constraint - ā Cost precomputation optimization - ā Partition DP with twist - ā Complete from brute force to optimal - ā TRUE baby-to-expert learning!
Key Difference from 253: Fixed parts vs minimize parts! ššāØ