Palindrome Partitioning

Problem: Given a string s, partition s such that every sub-string of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. 

Example: 

Input: s = "abcbm"
Output: 2
Explanation: The palindrome partitioning ["a","bcb", "m"] could be produced using 2 cut.

Approach: Use DP here. Maintain a 2D table say IsPlaindrome where IsPlaindrome [i][j] is true, only if sub-string s[i...j] is palindrome. Once it is filled, we can have another 1D table say MinCuts where MinCuts[i] will give the minimum number of cuts required to solve this problem for sub-string s[0...i].

Here is how we can fill MinCuts -

1. If s[0..i] is palindrome i.e. IsPlaindrome[0][i] is true then MinCuts[i] = 0.
2. if not then for each j = 0...i, take the min of 1 + C[j] and assign it to C[i]. Basically check by cutting at each and every index and take the minimum. We can optimize it bit with checking only if s[j+1...i] is palindrome.

        public int MinPalindromeCut(string s)

        {

            bool[,] isPlaindrome = new bool[s.Length, s.Length];

            // Every substring of length 1 is a palindrome

            for (int i = 0; i < s.Length; ++i)

            {

                isPlaindrome[i, i] = true;

            }

            // Initialize Palindrome table to according to s[i...j] is palindrome or not

            for (int length = 2; length <= s.Length; ++length)

            {

                for (int i = 0; i <= s.Length - length; ++i)

                {

                    int j = i + length - 1; // end index

                    isPlaindrome[i, j] = length == 2 ? s[i] == s[j] : s[i] == s[j] && isPlaindrome[i + 1, j - 1];

                }

            }

            int[] minCut = new int[s.Length];

            for (int i = 0; i < s.Length; ++i)

            {

                // If till s[0...i] is palindrome then no cut is required

                if (isPlaindrome[0, i])

                {

                    minCut[i] = 0;

                }

                else

                {

                    minCut[i] = int.MaxValue;

                    // Checking for each cut

                    for (int j = 0; j < i; ++j)

                    {

                        if (isPlaindrome[j + 1, i] && minCut[j] + 1 < minCut[i])

                        {

                            minCut[i] = minCut[j] + 1;

                        }

                    }

                }

            }

            return minCut[minCut.Length - 1];

        }

Complexity: O(n^2)