Example: Palindrome Partition Dynamic Programming

You are given a string and are tasked to find the minimum number of splits such that each substring is a palindrome.

x= a, b, c, b, m

Better solution $n^2$

• first we check if each substring is a palindrome
• we then use an array to measure the splits,
  • if 0..j is a palindrome, c[j] has 0 splits
  • otherwise, we check if we have an inner palindrome, in that case, if we find a palindrome at index i, the c[j] becomes 1 + the minimum split found before i => 1 + c[i-1]

optimalSplit(x)
    n = x.len
    d[0..n-1, 0..n-1]

    // first we check if each sequence is a palindrome
    for i = 0 to n-1
        d[i,i] = true

    for l = 2 to n
        for i = 0 to n - l
            j = i + l - 1
            if x[i] == x[j]
                if l == 2
                    d[i,j] = true
                else 
                    d[i,j] = d[i+1, j-1]
            
    c = [0..n-1] init to max
    
    for j = 0 to n-1
        if d[0, j]
            // x[0..j] is a palindrome
            c[j] = 0
        else 
            // find best split
            for i = 1 to j
                if d[i,j]
                    // x[i..j] is a palindrome
                    c[j] = min(c[j], 1 + c[i-1])
                    // we can track the splits here if we need to 

    // we can reconstruct the split as follows if we need it:
    // splits = []
    // k = n-1
    // while k >= 0:
    //     splits.append(s[k] + 1)  // Record the split point
    //     k = s[k]
    // splits.reverse()

    return c[n-1]

OLD SOLUTION $n^3$

• l=1 => If there is only one element, no splits are required

---	0	1	2	3	4
0	0
1		0
2			0
3				0
4					0

• l > 1 => i..j,
  • if i == j, check if it is a palindrome or find optimal split
  • if i != j => it is not a palindrome, optimal split

x= a, b, c, b, m

---	0	1	2	3	4
0	0	1
1		0	1
2			0	1
3				0	1
4					0

• a, b, c, b, m
  • a, b, c => a != c, i=0, j=2
    • min (1 + $X_{i..k}$ + $X_{k+1..k}$) for k = i to j, I can use the table to get the best value for each

---	0	1	2	3	4
0	0	1	2
1		0	1	0
2			0	1	2
3				0	1
4					0

• a, b, c, b, m

---	0	1	2	3	4
0	0	1	2	1	2
1		0	1	0	1
2			0	1	2
3				0	1
4					0

// x[0..n-1]
optimalPalindromeSplit(x)
    n = x.len
    // save min num of split
    d[0..n-1, 0..n-1]
    // save splits
    s[0..n-1, 0..n-1] initialized to -1

    for i = 0 to n-1
        // if there is only one char it is a palindrome so no split required
        d[i,i] = 0 

    for l = 2 to n
        for i = 0 to n-l-1
            j = i+l
            if i < n-1 && j > 0 && x[i] == x[j] && d[i+1, j-1] == 0 || is_palindrome(i, j, x)
                // all thing is a palindrome
                d[i,j] = 0
            else 
                // find optimal split
                d[i,j] = max
                for k = i to j-1
                    q = 1 + d[i,k] + d[k+1,j]
                    if q < d[i,j]
                        d[i,j] = q
                        s[i,j] = k

    print("Min num of splits is: " + d[0,n-1]
    i = 0
    j = n-1

    printSplit(i, j, s)

is_palindrome(x, i, j):
    while i < j:
        if x[i] != x[j]:
            return False
        i += 1
        j -= 1
    return True

printSplit(i, j, s)
    k = s[i,j]
    if k == -1
        return
    
    print("Split: " + k)
    printSplit(i, k, s)
    printSplit(k+1, j, s)