Driver code
using System ; using System . Collections . Generic ; class GFG { static int minCut ( string a ) { int [ ] cut = new int [ a . Length ] ; bool [ , ] palindrome = new bool [ a . Length , a . Length ] ; for ( int i = 0 ; i < a . Length ; i ++ ) { int minCut = i ; for ( int j = 0 ; j <= i ; j ++ ) { if ( a [ i ] == a [ j ] && ( i - j < 2 palindrome [ j + 1 , i - 1 ] ) ) { palindrome [ j , i ] = true ; minCut = Math . Min ( minCut , j == 0 ? 0 : ( cut [ j - 1 ] + 1 ) ) ; } } cut [ i ] = minCut ; } return cut [ a . Length - 1 ] ; } static void Main ( ) { Console . WriteLine ( minCut ( " aab " ) ) ; Console . WriteLine ( minCut ( " aabababaxx " ) ) ; } }