Palindrome Partitioning II

hard

Acceptance: 36%

Dynamic Programming

Given a string, find the fewest number of cuts required to partition it so that every resulting piece reads the same forwards and backwards.

Example 1:

Input:s = "abcba"

Output:0

Explanation: The entire string is already a palindrome, so no cuts are needed.

Example 2:

Input:s = "abcdef"

Output:5

Explanation: Each character must be its own partition, requiring 5 cuts.

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}