Given a string str, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Determine the fewest cuts needed for palindrome partitioning of the given string.
Example 1:
Input: str = "ababbbabbababa"
Output: 3
Explaination: After 3 partitioning substrings 
are "a", "babbbab", "b", "ababa".
Example 2:
Input: str = "aaabba"
Output: 1
Explaination: The substrings after 1
partitioning are "aa" and "abba".
Your Task:
You do not need to read input or print anything, Your task is to complete the function palindromicPartition() which takes the string str as the input parameter and returns the minimum number of partitions required.
Expected Time Complexity: O(n*n) [n is the length of the string str]
Expected Auxiliary Space: O(n*n)
Constraints:
1 ≤ length of str ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def palindromicPartition(self, string):

        # code here

Solutions:
class Solution:

	def palindromicPartition(self, s):
		dp = [[-1] * (len(s) + 1) for _ in range(len(s) + 1)]

		def dfs(s, i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			if i > j:
				return 0
			if self.isPal(s, i, j):
				return 0
			mx = len(s)
			for k in range(i, j):
				if self.isPal(s, i, k):
					t = dfs(s, k + 1, j) + 1
					mx = min(mx, t)
			dp[i][j] = mx
			return dp[i][j]
		return dfs(s, 0, len(s) - 1)

	def isPal(self, s, start, end):
		while start <= end:
			if s[start] != s[end]:
				return False
			start += 1
			end -= 1
		return True


class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = [[-1 for i in range(n + 2)] for j in range(n + 2)]

		def ispal(st):
			return st == st[::-1]

		def solve(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if ispal(s[i:j + 1]):
				return 0
			mn = int(1000000000.0)
			for k in range(i, j):
				if ispal(s[i:k + 1]):
					temp = solve(k + 1, j) + 1
					mn = min(mn, temp)
			dp[i][j] = mn
			return mn
		x = solve(0, n - 1)
		return x


class Solution:

	def palindromicPartition(self, a):
		cut = [0 for i in range(len(a))]
		palindrome = [[False for i in range(len(a))] for j in range(len(a))]
		for i in range(len(a)):
			minCut = i
			for j in range(i + 1):
				if a[i] == a[j] and (i - j < 2 or palindrome[j + 1][i - 1]):
					palindrome[j][i] = True
					minCut = min(minCut, 0 if j == 0 else cut[j - 1] + 1)
			cut[i] = minCut
		return cut[len(a) - 1]


import numpy as np
import sys

class Solution:

	def dp_sol(self, string):
		len_s = len(string)
		dp = np.array([[0] * len_s] * len_s)
		for i in range(len_s):
			for j in range(i, -1, -1):
				if i == j:
					dp[j][i] = 0
				if i == j + 1:
					if string[i] == string[j]:
						dp[j][i] = 0
					else:
						dp[j][i] = 1
				else:
					start = j
					end = i
					while start < end and string[start] == string[end]:
						start = start + 1
						end = end - 1
					if start >= end:
						dp[j][i] = 0
					else:
						temp = sys.maxsize
						for k in range(j, i):
							temp = min(temp, 1 + dp[j][k] + dp[k + 1][i])
						dp[j][i] = temp
		return dp[0][len_s - 1]

	def dp_sol2(self, string):
		len_s = len(string)
		dp = np.array([[False] * len_s] * len_s)
		for i in range(len_s):
			for j in range(i + 1):
				if i == j:
					dp[j][i] = True
				elif j + 1 == i and string[i] == string[j]:
					dp[j][i] = True
				elif string[j] == string[i] and dp[j + 1][i - 1]:
					dp[j][i] = True
		p = np.array([len_s] * len_s)
		for i in range(len_s):
			if dp[0][i] == True:
				p[i] = 0
			else:
				for j in range(i):
					if dp[j + 1][i]:
						p[i] = min(p[i], p[j] + 1)
		return p[len_s - 1]

	def palindromicPartition(self, string):
		return self.dp_sol2(string)


class Solution:

	def isPalindrome(self, string, a, b):
		while a <= b:
			if string[a] != string[b]:
				return False
			a += 1
			b -= 1
		return True

	def palindromicPartition(self, string):
		n = len(string)
		dp = [-1 for _ in range(n + 1)]
		dp[n] = 0
		for i in range(n - 1, -1, -1):
			minCuts = float('inf')
			for j in range(i, n):
				if self.isPalindrome(string, i, j):
					minCuts = min(minCuts, 1 + dp[j + 1])
			dp[i] = minCuts
		return dp[0] - 1


def helper(string, i, n, dp, ans):
	ans[0] = 0
	for j in range(1, n):
		if dp[0][j]:
			ans[j] = 0
		else:
			temp = int(1000000000.0)
			for i in range(j, 0, -1):
				if dp[i][j]:
					temp = min(temp, ans[i - 1])
			ans[j] = temp + 1

class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [[False for _ in range(n)] for _ in range(n)]
		for j in range(n):
			for i in range(n):
				if j - i == 0 and i == j:
					dp[i][j] = True
				elif j - i == 1 and string[i] == string[j]:
					dp[i][j] = True
				elif j - i >= 2 and string[i] == string[j] and (dp[i + 1][j - 1] == True):
					dp[i][j] = True
		ans = [0] * n
		helper(string, 0, n, dp, ans)
		return ans[n - 1]


class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = [[-1 for i in range(0, n + 2)] for j in range(0, n + 2)]

		def getAns(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if isPal(s, i, j):
				return 0
			mn = int(1000000000.0)
			for k in range(i, j):
				if isPal(s, i, k):
					temp = getAns(k + 1, j) + 1
					mn = min(mn, temp)
			dp[i][j] = mn
			return mn

		def isPal(s, start, end):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True
		return getAns(0, n - 1)


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [-1 for i in range(n)]
		return self.f(0, n, string, dp) - 1

	def f(self, i, n, string, dp):
		mincost = float('inf')
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		for j in range(i, n):
			if self.isPalindrome(string, i, j):
				cost = 1 + self.f(j + 1, n, string, dp)
				mincost = min(mincost, cost)
		dp[i] = mincost
		return dp[i]

	def isPalindrome(self, string, i, j):
		while i < j:
			if string[i] != string[j]:
				return False
			i += 1
			j -= 1
		return True


class Solution:

	def palindromicPartition(self, string: str) -> int:
		n = len(string)
		P = [[False for _ in range(n)] for _ in range(n)]
		for i in range(n):
			P[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					P[i][j] = string[i] == string[j]
				else:
					P[i][j] = string[i] == string[j] and P[i + 1][j - 1]
		cuts = [0] * n
		for i in range(n):
			if P[0][i]:
				cuts[i] = 0
			else:
				cuts[i] = float('inf')
				for j in range(i):
					if P[j + 1][i] and cuts[j] + 1 < cuts[i]:
						cuts[i] = cuts[j] + 1
		return cuts[n - 1]


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [0 for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			minCuts = float('inf')
			for j in range(i, n):
				if self.isPalindrome(string[i:j + 1]):
					cuts = 1 + dp[j + 1]
					minCuts = min(cuts, minCuts)
			dp[i] = minCuts
		return dp[0] - 1

	def isPalindrome(self, x):
		return x == x[::-1]


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		P = [[False] * n for _ in range(n)]
		for i in range(n):
			P[i][i] = True
		for i in range(n - 1):
			P[i][i + 1] = string[i] == string[i + 1]
		for l in range(3, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				P[i][j] = string[i] == string[j] and P[i + 1][j - 1]
		C = [i for i in range(n)]
		for i in range(n):
			if P[0][i]:
				C[i] = 0
			else:
				for j in range(i):
					if P[j + 1][i]:
						C[i] = min(C[i], C[j] + 1)
		return C[n - 1]


class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		C = [0] * n
		P = [[False for i in range(n)] for i in range(n)]
		for i in range(n):
			P[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					P[i][j] = s[i] == s[j]
				else:
					P[i][j] = (s[i] == s[j]) & P[i + 1][j - 1]
		for i in range(n):
			if P[0][i]:
				C[i] = 0
			else:
				C[i] = 1 << 32
				for j in range(i):
					if P[j + 1][i] == True and C[j] + 1 < C[i]:
						C[i] = C[j] + 1
		return C[n - 1]


class Solution:

	def __init__(self):
		self.res = -float('inf')

	def check_palin(self, x):
		n = len(x)
		for i in range(n // 2):
			if x[i] != x[-i - 1]:
				return False
		return True

	def solve(self, i, j, st, dp):
		if i >= j:
			return 0
		if self.check_palin(st[i:j + 1]):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		min_cut = float('inf')
		for ind in range(i, j):
			if self.check_palin(st[i:ind + 1]):
				x = self.solve(ind + 1, j, st, dp) + 1
				min_cut = min(min_cut, x)
		dp[i][j] = min_cut
		return dp[i][j]

	def palindromicPartition(self, string):
		n = len(string)
		dp = [[-1 for i in range(n + 2)] for j in range(n + 2)]
		r = self.solve(0, n - 1, string, dp)
		return r


class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = [[-1 for i in range(n + 2)] for j in range(n + 2)]

		def ispal(st):
			return st == st[::-1]

		def solve(i, j):
			if i >= j or ispal(s[i:j + 1]):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			mn = float('inf')
			for k in range(i, j):
				if ispal(s[i:k + 1]):
					temp = solve(k + 1, j) + 1
					mn = min(mn, temp)
			dp[i][j] = mn
			return mn
		x = solve(0, n - 1)
		return x


class Solution:

	def palindromicPartition(self, string: str) -> int:
		n = len(string)
		dp = [[False] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = True
		for length in range(2, n + 1):
			for i in range(n - length + 1):
				j = i + length - 1
				if string[i] == string[j] and (length == 2 or dp[i + 1][j - 1]):
					dp[i][j] = True
		cuts = [float('inf')] * n
		for i in range(n):
			if dp[0][i]:
				cuts[i] = 0
			else:
				for j in range(i):
					if dp[j + 1][i]:
						cuts[i] = min(cuts[i], cuts[j] + 1)
		return cuts[n - 1]


class Solution:

	def palindromicPartition(self, s):

		def check(i, j, s):
			while i < j:
				if s[i] != s[j]:
					return False
				i += 1
				j -= 1
			return True
		dp = [-1] * len(s)

		def f(i, s):
			if i == len(s):
				return 0
			minCnt = 10 ** 9
			if dp[i] != -1:
				return dp[i]
			for j in range(i, len(s)):
				if check(i, j, s):
					cnt = 1 + f(j + 1, s)
					minCnt = min(minCnt, cnt)
			dp[i] = minCnt
			return dp[i]
		return f(0, s) - 1


class Solution:

	def palindromicPartition(self, string):

		def ispal(s):
			return s == s[::-1]

		def solve(i, j, string):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if ispal(string[i:j + 1]):
				return 0
			ans = 10000000000.0
			for k in range(i, j):
				if ispal(string[i:k + 1]):
					temp = 1 + solve(k + 1, j, string)
					ans = min(ans, temp)
			dp[i][j] = ans
			return dp[i][j]
		n = len(string)
		dp = [[-1] * 1001 for i in range(1001)]
		return solve(0, n - 1, string)


class Solution:

	def palindromicPartition(self, s):

		def calc(i):
			if i == len(s):
				return 0
			if dp[i] != -1:
				return dp[i]
			else:
				mxc = float('inf')
				for k in range(i, len(s)):
					if s[i:k + 1] == s[i:k + 1][::-1]:
						cnt = 1 + calc(k + 1)
						mxc = min(mxc, cnt)
				dp[i] = mxc
				return dp[i]
		dp = [-1 for i in range(len(s) + 1)]
		return calc(0) - 1


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		if n != 0:
			dp = [[False] * n for i in range(n)]
			for i in range(n):
				dp[i][i] = True
				if i != n - 1:
					if string[i] == string[i + 1]:
						dp[i][i + 1] = True
			for c in range(2, n):
				i = 0
				j = c
				while i < n and j < n:
					if string[i] != string[j]:
						dp[i][j] = False
					else:
						dp[i][j] = dp[i + 1][j - 1]
					i += 1
					j += 1
			mc = [0] * len(string)
			mc[0] = 0
			for i in range(1, n):
				if dp[0][i] == True:
					mc[i] = 0
				else:
					mc[i] = 100000
					for k in range(1, i + 1):
						if dp[k][i]:
							mc[i] = min(mc[i], 1 + mc[k - 1])
			return mc[n - 1]


class Solution:
	isPalindrome = []

	def palindromicPartition(self, string):
		self.isPalindrome = [[False for i in range(len(string))] for j in range(len(string))]

		def populateIsPalindromeDP():
			for i in range(0, len(string)):
				for j in range(0, len(string) - i):
					if i == 0:
						self.isPalindrome[j][j] = True
					elif i == 1:
						if string[j] == string[j + 1]:
							self.isPalindrome[j][j + 1] = True
					elif string[j] == string[j + i] and self.isPalindrome[j + 1][j + i - 1]:
						self.isPalindrome[j][j + i] = True
		populateIsPalindromeDP()
		dp = [0 for i in range(len(string) + 1)]
		for i in range(1, len(string) + 1):
			dp[i] = dp[i - 1] + 1
			if self.isPalindrome[0][i - 1]:
				dp[i] = 0
				continue
			for j in range(0, i):
				if self.isPalindrome[j + 1 - 1][i - 1]:
					dp[i] = min(dp[i], 1 + dp[j])
		return dp[-1]


class Solution:

	def ispalindrome(self, start, end, string):
		while start < end:
			if string[start] != string[end]:
				return False
			start += 1
			end -= 1
		return True

	def palindromicPartition(self, string):
		n = len(string)
		dp = [0 for i in range(n + 1)]

		def rec(idx):
			if idx == n:
				return 0
			if dp[idx] != -1:
				return dp[idx]
			maxi = float('inf')
			(p, np) = (float('inf'), float('inf'))
			for i in range(idx, n):
				if self.ispalindrome(idx, i, string):
					p = 1 + rec(i + 1)
					maxi = min(maxi, p)
			dp[idx] = maxi
			return dp[idx]
		for idx in range(n - 1, -1, -1):
			maxi = float('inf')
			(p, np) = (float('inf'), float('inf'))
			for i in range(idx, n):
				if self.ispalindrome(idx, i, string):
					p = 1 + dp[i + 1]
					maxi = min(maxi, p)
			dp[idx] = maxi
		return dp[0] - 1


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [0] * n
		pal = [[False] * n for _ in range(n)]
		for i in range(n):
			pal[i][i] = True
		for l in range(2, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				if l == 2:
					pal[i][j] = string[i] == string[j]
				else:
					pal[i][j] = string[i] == string[j] and pal[i + 1][j - 1]
		for i in range(n):
			min_cuts = i
			for j in range(i + 1):
				if pal[j][i]:
					if j == 0:
						min_cuts = 0
					else:
						min_cuts = min(min_cuts, dp[j - 1] + 1)
			dp[i] = min_cuts
		return dp[n - 1]


class Solution:

	def palindromicPartition(self, string):
		dp = {}
		return self.helper(string, dp)

	def helper(self, string, dp):
		n = len(string)
		if n == 0:
			dp[string] = 0
			return 0
		if string in dp:
			return dp[string]
		if string == string[::-1]:
			dp[string] = 0
			return 0
		minimum = float('inf')
		for i in range(1, n + 1):
			if string[:i] == string[:i][::-1]:
				minimum = min(minimum, 1 + self.helper(string[i:], dp))
		dp[string] = minimum
		return dp[string]


class Solution:

	def palindromicPartition(self, string):
		n = len(string)

		def check_pali(s, e):
			(i, j) = (s, e)
			while i < j:
				if string[i] != string[j]:
					return False
				i += 1
				j -= 1
			return True
		maxi = 10 ** 9
		dp = [-1] * n

		def find(start):
			if start == n or check_pali(start, n - 1):
				return 0
			if dp[start] != -1:
				return dp[start]
			ans = maxi
			for i in range(start, n):
				if check_pali(start, i):
					ans = min(ans, find(i + 1))
			dp[start] = ans + 1
			return dp[start]
		return find(0)


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [[False for i in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					dp[i][j] = string[i] == string[j]
				elif string[i] == string[j]:
					dp[i][j] = dp[i + 1][j - 1]
		c = [0] * n
		for i in range(1, n):
			if dp[0][i]:
				c[i] = 0
			else:
				c[i] = float('inf')
				for j in range(i):
					if dp[j + 1][i] and c[j] + 1 < c[i]:
						c[i] = c[j] + 1
		return c[n - 1]


class Solution:

	def palindromicPartition(self, string):
		n = len(string)

		def ispalindrome(strs, st, end):
			while st <= end:
				if strs[st] == strs[end]:
					st += 1
					end -= 1
				else:
					return False
			return True
		dp = [-1] * (n + 1)

		def findsol(string, i, n):
			if i == n:
				return 0
			if dp[i] != -1:
				return dp[i]
			minval = 999999999
			for x in range(i + 1, n + 1):
				if ispalindrome(string, i, x - 1) == True:
					minval = min(minval, findsol(string, x, n))
			dp[i] = minval + 1
			return minval + 1
		return findsol(string, 0, n) - 1


class Solution:

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

	def palindromicPartition(self, string):
		n = len(string)
		dp1 = [[False] * n for _ in range(n)]
		dp2 = [0] * n
		for i in range(n):
			dp1[i][i] = True
		for length in range(2, n + 1):
			for start in range(n - length + 1):
				end = start + length - 1
				if length == 2:
					dp1[start][end] = string[start] == string[end]
				else:
					dp1[start][end] = string[start] == string[end] and dp1[start + 1][end - 1]
		for i in range(n):
			if dp1[0][i]:
				dp2[i] = 0
			else:
				dp2[i] = float('inf')
				for j in range(i):
					if dp1[j + 1][i] and dp2[j] + 1 < dp2[i]:
						dp2[i] = dp2[j] + 1
		return dp2[n - 1]


class Solution:

	def palindromicPartition(self, s):
		N = len(string)
		dp = [[-1 for i in range(N + 2)] for j in range(N + 2)]

		def ispalindrome(s1):
			return s1 == s1[::-1]

		def solve(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if ispalindrome(s[i:j + 1]):
				return 0
			ans = 999999
			for k in range(i, j):
				if ispalindrome(s[i:k + 1]):
					temp = solve(k + 1, j) + 1
					ans = min(ans, temp)
			dp[i][j] = ans
			return ans
		return solve(0, N - 1)


def check(s):
	if s == s[::-1]:
		return True
	else:
		return False

class Solution:

	def palindromicPartition(self, string):
		dp = {}

		def fun(s, i, j):
			if i >= j:
				return 0
			if check(s[i:j]):
				return 0
			if (i, j) in dp:
				return dp[i, j]
			m = float('inf')
			for k in range(i, j):
				if check(s[i:k + 1]):
					temp = fun(s, k + 1, j) + 1
					m = min(m, temp)
			dp[i, j] = m
			return dp[i, j]
		return fun(string, 0, len(string))


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [0] * (n + 1)
		dp[n] = 0
		for i in reversed(range(n)):
			minCost = float('inf')
			for j in range(i, n):
				cur_string = string[i:j + 1]
				if self.isPalindrome(cur_string):
					cost = 1 + dp[j + 1]
					minCost = min(minCost, cost)
			dp[i] = minCost
		return dp[0] - 1

	def isPalindrome(self, cur_string):
		left = 0
		right = len(cur_string) - 1
		while left < right:
			if cur_string[left] != cur_string[right]:
				return False
			left += 1
			right -= 1
		return True


class Solution:

	def p(self, s):
		l = 0
		r = len(s) - 1
		while l < r:
			if s[l] != s[r]:
				return False
			l += 1
			r -= 1
		return True

	def palindromicPartition(self, string):
		dp = [len(string) + 1 for i in range(len(string) + 1)]
		dp[0] = -1
		for i in range(1, len(string) + 1):
			for j in range(i):
				if self.p(string[j:i]):
					dp[i] = min(dp[i], 1 + dp[j])
		return dp[-1]


class Solution:

	def palindromicPartition(self, string):
		is_pali = [[False for i in range(len(string))] for j in range(len(string))]
		for k in range(len(string)):
			(i, j) = (0, k)
			while j < len(string):
				if k == 0:
					is_pali[i][j] = True
				elif k == 1:
					if string[i] == string[j]:
						is_pali[i][j] = True
				elif string[i] == string[j] and is_pali[i + 1][j - 1] is True:
					is_pali[i][j] = True
				i += 1
				j += 1
		dp = [float('inf')] * len(string)
		dp[0] = 0
		for i in range(1, len(string)):
			if is_pali[0][i] is True:
				dp[i] = 0
			else:
				for j in range(i, 0, -1):
					if is_pali[j][i] is True:
						dp[i] = min(dp[i], 1 + dp[j - 1])
		return dp[-1]


def ispallindrome(string, i, j):
	if string == '':
		return False
	while i < j:
		if string[i] != string[j]:
			return False
		i += 1
		j += -1
	return True

class Solution:

	def solve(self, arr, ind, dp):
		if ind == len(arr):
			return 0
		partition = 0
		MIN = float('inf')
		if dp[ind] != -1:
			return dp[ind]
		for i in range(ind, len(arr)):
			if ispallindrome(arr, ind, i):
				partition = 1 + self.solve(arr, i + 1, dp)
			MIN = min(MIN, partition)
		dp[ind] = MIN
		return MIN

	def palindromicPartition(self, string):
		dp = [-1 for _ in range(len(string))]
		return self.solve(string, 0, dp) - 1


class Solution:

	def palindromicPartition(self, string):
		n = len(string)

		def ispalindrome(start, end, str):
			while start < end:
				if str[start] != str[end]:
					return False
				start += 1
				end -= 1
			return True
		dp = [0 for i in range(n + 1)]

		def rec(idx):
			if idx == n:
				return 0
			if dp[idx] != -1:
				return dp[idx]
			mini = int(1000000000.0)
			for i in range(idx, n):
				if ispalindrome(idx, i, string):
					cost = 1 + rec(i + 1)
					mini = min(mini, cost)
			dp[idx] = mini
			return dp[idx]
		for idx in range(n - 1, -1, -1):
			mini = int(1000000000.0)
			for i in range(idx, n):
				if ispalindrome(idx, i, string):
					cost = 1 + dp[i + 1]
					mini = min(mini, cost)
			dp[idx] = mini
		return dp[0] - 1


def is_palindrome(s):
	return s == s[::-1]

class Solution:

	def helper(self, s):
		if self.d.get(s) is not None:
			return self.d[s]
		if not s:
			return 0
		ans = 10 ** 9
		for i in range(len(s)):
			if is_palindrome(s[:i + 1]):
				ans = min(ans, 1 + self.helper(s[i + 1:]))
		self.d[s] = ans
		return ans

	def palindromicPartition(self, string):
		self.d = {}
		return self.helper(string) - 1


class Solution:

	def palindromicPartition(self, s):

		def checkPalindrome(string, i, j):
			(l, r) = (i, j)
			while l < r:
				if string[l] != string[r]:
					return False
				l += 1
				r -= 1
			return True

		def solve(string, i, j, dp):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if checkPalindrome(string, i, j):
				dp[i][j] = 0
				return 0
			ans = float('inf')
			for k in range(i, j):
				if checkPalindrome(string, i, k):
					temp = 1 + solve(string, k + 1, j, dp)
					ans = min(ans, temp)
			dp[i][j] = ans
			return ans
		n = len(s)
		dp = [[-1 for j in range(n + 1)] for i in range(n + 1)]
		ans = solve(s, 0, n - 1, dp)
		return ans


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		t = [[-1 for _ in range(n + 2)] for _ in range(n + 2)]

		def isPalin(s):
			return s == s[::-1]

		def solve(i, j):
			if i >= j:
				return 0
			if t[i][j] != -1:
				return t[i][j]
			if isPalin(string[i:j + 1]):
				return 0
			mn = int(1000000000.0)
			for k in range(i, j):
				if isPalin(string[i:k + 1]):
					temp = solve(k + 1, j) + 1
					mn = min(mn, temp)
			t[i][j] = mn
			return mn
		return solve(0, n - 1)


class Solution:

	def ispallindrome(self, s, i, j):
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def palindromicPartition(self, s):
		n = len(s)
		dp = [[-1 for i in range(501)] for j in range(501)]

		def helper(i, j):
			if i >= j:
				dp[i][j] = 0
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			if self.ispallindrome(s, i, j):
				dp[i][j] = 0
				return 0
			ans = 510
			for k in range(i, j):
				if self.ispallindrome(s, i, k):
					temp = 1 + helper(i, k) + helper(k + 1, j)
					ans = min(ans, temp)
			dp[i][j] = ans
			return dp[i][j]
		return helper(0, n - 1)


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]

		def ispalindromic(string):
			return string == string[::-1]

		def func(string, i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if ispalindromic(string[i:j + 1]):
				return 0
			c = 100000
			for k in range(i, j):
				if ispalindromic(string[i:k + 1]):
					if dp[k + 1][j] != -1:
						c2 = dp[k + 1][j]
					else:
						c2 = func(string, k + 1, j)
					temp = c2 + 1
				c = min(c, temp)
				dp[i][j] = c
			return dp[i][j]
		return func(string, 0, n - 1)


class Solution:

	def palindromicPartition(self, str):
		n = len(str)
		dp = [0] * n
		palindrome = [[False] * n for _ in range(n)]
		for i in range(n):
			min_cut = i
			for j in range(i + 1):
				if str[i] == str[j] and (i - j < 2 or palindrome[j + 1][i - 1]):
					palindrome[j][i] = True
					if j == 0:
						min_cut = 0
					else:
						min_cut = min(min_cut, dp[j - 1] + 1)
			dp[i] = min_cut
		return dp[n - 1]


import sys

class Solution:

	def isPalindrome(self, str, i, j):
		while i < j:
			if str[i] != str[j]:
				return False
			i += 1
			j -= 1
		return True

	def palindromicPartition(self, str):
		n = len(str)
		dp = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			mn = sys.maxsize
			for cut in range(i, n):
				if self.isPalindrome(str, i, cut):
					cost = 1 + dp[cut + 1]
					mn = min(mn, cost)
			dp[i] = mn
		return dp[0] - 1


class Solution:

	def fun(self, i, s, n, dp):
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		temp = ''
		mini = float('inf')
		for j in range(i, n):
			temp += s[j]
			if temp == temp[::-1]:
				cost = 1 + self.fun(j + 1, s, n, dp)
				mini = min(mini, cost)
		dp[i] = mini
		return dp[i]

	def palindromicPartition(self, string):
		dp = [-1 for i in range(len(string) + 1)]
		return self.fun(0, string, len(string), dp) - 1


class Solution:

	def palindromicPartition(self, S):

		def palind(f):
			l = len(f)
			for i in range(l // 2):
				if f[i] != f[l - i - 1]:
					return 0
			return 1

		def manu(i, n, s):
			if i == n:
				return 0
			if dp[i][n] != -1:
				return dp[i][n]
			x = ''
			mini = 10 ** 9
			for j in range(i, n):
				x += s[j]
				if palind(x):
					c = 1 + manu(j + 1, n, s)
					mini = min(mini, c)
			dp[i][n] = mini
			return mini
		dp = [[-1 for i in range(len(S) + 1)] for i in range(len(S) + 1)]
		return manu(0, len(S), S) - 1


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		c = [0] * n
		p = [[False for i in range(n)] for i in range(n)]
		for i in range(n):
			p[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					p[i][j] = string[i] == string[j]
				else:
					p[i][j] = string[i] == string[j] and p[i + 1][j - 1]
		for i in range(n):
			if p[0][i] == True:
				c[i] = 0
			else:
				c[i] = 25000
				for j in range(i):
					if p[j + 1][i] and c[j] + 1 < c[i]:
						c[i] = c[j] + 1
		return c[n - 1]


class Solution:

	def palindromicPartition(self, S):
		N = len(S)
		isp = [[True] * N for _ in range(N)]
		for add in range(1, N):
			for j in range(N - add):
				isp[j][j + add] = S[j] == S[j + add] and isp[j + 1][j + add - 1]
		dp = [1] * N + [0]
		for i in range(1, N):
			v = 1 + dp[i - 1]
			for j in range(i):
				if S[i] == S[j] and isp[j + 1][i - 1]:
					v = min(v, dp[j - 1] + 1)
			dp[i] = v
		return dp[N - 1] - 1


import math

class Solution:

	def solve(self, i, j, string, dp, ispall):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if ispall[i][j] == 1:
			dp[i][j] = 0
			return dp[i][j]
		currmin = float('INF')
		for p in range(i, j + 1):
			if ispall[i][p]:
				currmin = min(currmin, 1 + self.solve(p + 1, j, string, dp, ispall))
		dp[i][j] = currmin
		return dp[i][j]

	def palindromicPartition(self, string):
		ispall = [[0 for i in range(len(string))] for t in range(len(string))]
		for i in range(len(string)):
			for j in range(i, len(string)):
				curr = string[i:j + 1]
				flag = 1
				(ptr1, ptr2) = (0, j - i)
				while ptr1 <= ptr2:
					if curr[ptr1] != curr[ptr2]:
						flag = 0
						break
					ptr1 += 1
					ptr2 -= 1
				ispall[i][j] = flag
		dp = [[-1 for i in range(len(string))] for t in range(len(string))]
		return self.solve(0, len(string) - 1, string, dp, ispall)


class Solution:

	def palindromicPartition(self, string):
		dp = [0 for i in range(len(string))]
		p = [[False for i in range(len(string))] for j in range(len(string))]
		for i in range(len(string)):
			m = i
			for j in range(i + 1):
				if string[i] == string[j] and (i - j < 2 or p[j + 1][i - 1]):
					p[j][i] = True
					m = min(m, 0 if j == 0 else dp[j - 1] + 1)
			dp[i] = m
		return dp[len(string) - 1]


class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		p = [[False] * (n + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			cost = float('inf')
			for k in range(i, 0, -1):
				if s[k - 1] == s[i - 1] and (i - k <= 2 or p[k][i - 2]):
					p[k - 1][i - 1] = True
					curr = 1 + dp[k - 1]
					cost = min(cost, curr)
			dp[i] = cost
		return dp[n] - 1


class Solution:

	def palindromicPartition(self, s: str) -> int:
		n = len(s)
		dp = [[False] * n for _ in range(n)]
		cuts = [0] * n
		for i in range(n):
			dp[i][i] = True
			for j in range(i):
				if s[i] == s[j] and (i == j + 1 or dp[j + 1][i - 1]):
					dp[j][i] = True
		for i in range(n):
			if dp[0][i]:
				cuts[i] = 0
			else:
				cuts[i] = i
				for j in range(1, i + 1):
					if dp[j][i]:
						cuts[i] = min(cuts[i], cuts[j - 1] + 1)
		return cuts[n - 1]


from functools import lru_cache

class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = {}
		palindrome = [[False for _ in range(n)] for _ in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if s[i] == s[j]:
					if j - i + 1 <= 2:
						palindrome[i][j] = True
					else:
						palindrome[i][j] = palindrome[i + 1][j - 1]

		def fun(i):
			if i == n:
				return 0
			if i in dp:
				return dp[i]
			minc = float('inf')
			for j in range(i, n):
				if palindrome[i][j]:
					minc = min(minc, 1 + fun(j + 1))
			dp[i] = minc
			return minc
		return fun(0) - 1


from functools import lru_cache

class Solution:

	def palindromicPartition(self, s):
		n = len(s)
		dp = {}

		def isPalindrome(l, r):
			r += 1
			d = (r - l) // 2
			for i in range(d):
				if s[l + i] != s[r - 1 - i]:
					return False
			return True

		def fun(i):
			if i == n:
				return 0
			if i in dp:
				return dp[i]
			minc = float('inf')
			for j in range(i, n):
				if isPalindrome(i, j):
					minc = min(minc, 1 + fun(j + 1))
			dp[i] = minc
			return minc
		return fun(0) - 1


def chk(l, r, s):
	while l < r:
		if s[l] == s[r]:
			r -= 1
			l += 1
		else:
			return False
	return True

def f(l, r, s, dp):
	if (l, r) in dp:
		return dp[l, r]
	if chk(l, r, s):
		return 1
	ans = r - l + 1
	for i in range(l, r):
		if chk(l, i, s):
			ans = min(ans, 1 + f(i + 1, r, s, dp))
	dp[l, r] = ans
	return ans

class Solution:

	def palindromicPartition(self, string):
		dp = {}
		s = list(string)
		return f(0, len(s) - 1, s, dp) - 1


class Solution:

	def isPalin(self, i, j, string):
		while i < j:
			if string[i] != string[j]:
				return False
			j -= 1
			i += 1
		return True

	def recur(self, i, string, n, dp, dpP):
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		mini = float('inf')
		for j in range(i, n):
			if self.isPalin(i, j, string):
				cost = 1 + self.recur(j + 1, string, n, dp, dpP)
				mini = min(mini, cost)
		dp[i] = mini
		return mini

	def palindromicPartition(self, string):
		n = len(string)
		dp = [float('inf') for i in range(len(string))]
		dp.append(0)
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if self.isPalin(i, j, string):
					cost = 1 + dp[j + 1]
					dp[i] = min(dp[i], cost)
		return dp[0] - 1


import sys

class Solution:

	def palindromicPartition(self, str1):
		n = len(str1)
		C = [0] * (n + 1)
		P = [[False for x in range(n + 1)] for y in range(n + 1)]
		for i in range(n):
			P[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					P[i][j] = str1[i] == str1[j]
				else:
					P[i][j] = str1[i] == str1[j] and P[i + 1][j - 1]
		for i in range(n):
			if P[0][i] == True:
				C[i] = 0
			else:
				C[i] = sys.maxsize
				for j in range(i):
					if P[j + 1][i] == True and 1 + C[j] < C[i]:
						C[i] = 1 + C[j]
		return C[n - 1]


class Solution:

	def palindromicPartition(self, string):
		i = 0
		j = len(string) - 1
		dp = [[-1 for i in range(len(string) + 1)] for j in range(len(string) + 1)]
		ans = self.solve(string, i, j, dp)
		return ans

	def isPalindrome(self, string):
		return string == string[::-1]

	def solve(self, string, i, j, dp):
		if i >= j or self.isPalindrome(string[i:j + 1]):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		mini = float('inf')
		for k in range(i, j):
			if self.isPalindrome(string[i:k + 1]):
				temp_ans = 1 + self.solve(string, k + 1, j, dp)
				if temp_ans < mini:
					mini = temp_ans
		dp[i][j] = mini
		return dp[i][j]


class Solution:

	def palindromicPartition(self, string):
		s = string

		def solve(s, i, j):
			if temp[i][j] != -1:
				return temp[i][j]
			if i >= j or s[i:j + 1] == s[i:j + 1][::-1]:
				return 0
			ans = float('infinity')
			for k in range(i, j):
				if s[i:k + 1] == s[i:k + 1][::-1]:
					left = solve(s, k + 1, j)
				tmp = 1 + left
				ans = min(ans, tmp)
			temp[i][j] = ans
			return temp[i][j]
		temp = [[-1] * 502 for i in range(502)]
		return solve(s, 0, len(s) - 1)


class Solution:

	def palindromicPartition(self, string):

		def pal(i, j):
			if i >= j or string[i:j + 1] == string[i:j + 1][::-1]:
				dp[i] = 0
				return 0
			if dp[i] != -1:
				return dp[i]
			count = 10 ** 10
			for k in range(i, j):
				count = min(count, pal(i, k) + pal(k + 1, j) + 1)
				dp[i] = count
			return count
		i = 0
		j = len(string)
		dp = [-1 for k in range(j + 1)]
		return pal(i, j)


class Solution:

	def palindromicPartition(self, str):
		n = len(str)
		P = [[False for _ in range(n)] for _ in range(n)]
		for i in range(n):
			P[i][i] = True
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				if L == 2:
					P[i][j] = str[i] == str[j]
				else:
					P[i][j] = str[i] == str[j] and P[i + 1][j - 1]
		C = [float('inf') for _ in range(n)]
		for j in range(n):
			if P[0][j]:
				C[j] = 0
			else:
				for i in range(j):
					if P[i + 1][j]:
						C[j] = min(C[j], C[i] + 1)
		return C[n - 1]


class Solution:

	def palindromicPartition(self, str):
		n = len(str)
		dp = [[False] * n for i in range(n)]
		for g in range(0, n):
			for (i, j) in zip(range(0, n), range(g, n)):
				if g == 0:
					dp[i][j] = True
				elif g == 1:
					if str[i] == str[j]:
						dp[i][j] = True
					else:
						dp[i][j] = False
				elif str[i] == str[j] and dp[i + 1][j - 1] == True:
					dp[i][j] = True
				else:
					dp[i][j] = False
		if dp[0][n - 1] == True:
			return 0
		ans = [int(x) for x in range(n + 1)]
		ans[0] = 0
		ans[1] = 0
		ans[2] = 0
		if str[0] != str[1]:
			ans[2] += 1
		for i in range(3, n + 1):
			for j in range(i, 0, -1):
				if dp[j - 1][i - 1] == True:
					ans[i] = min(ans[i], ans[j - 1] + 1)
		return ans[n]


import sys

class Solution:

	def is_palindrome(self, strt, end, st):
		while strt < end:
			if st[strt] != st[end]:
				return False
			strt += 1
			end -= 1
		return True

	def get_cuts(self, i, j, string, dp):
		if i >= j:
			return 0
		if self.is_palindrome(i, j, string):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		ans = sys.maxsize
		curr_min = sys.maxsize
		for k in range(i, j):
			if self.is_palindrome(i, k, string):
				curr_min = 1 + self.get_cuts(k + 1, j, string, dp)
				ans = min(curr_min, ans)
		dp[i][j] = ans
		return ans

	def palindromicPartition(self, string):
		dp = [[-1 for x in range(len(string) + 1)] for y in range(len(string) + 1)]
		return self.get_cuts(0, len(string) - 1, string, dp)


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def palindromicPartition(self, string):
		d = dict()

		def dfs(s, i, j):
			if i == j:
				s1 = s[i:j + 1]
				if s1 == s1[::-1]:
					return -1
				return 10 ** 9
			if d.get((i, j)) != None:
				return d[i, j]
			y = 10 ** 9
			for k in range(i, j):
				s1 = s[i:k + 1]
				if s1 == s1[::-1]:
					a = 1 + dfs(s, k + 1, j)
					y = min(y, a)
			d[i, j] = y
			return y
		return dfs(string, 0, len(string))


class Solution:

	def palindromicPartition(self, string):
		S = string
		n = len(S)
		hmap = {}

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

		def palin_partition(arr, i, j):
			if i >= j or is_palindrome(arr, i, j):
				hmap[i, j] = 0
				return 0
			mini = 1000000000.0
			if (i, j) not in hmap:
				for k in range(i, j):
					if is_palindrome(arr, i, k):
						if (k + 1, j) not in hmap:
							hmap[k + 1, j] = palin_partition(arr, k + 1, j)
						temp_ans = 1 + hmap[k + 1, j]
						mini = min(mini, temp_ans)
				hmap[i, j] = mini
			return hmap[i, j]
		return palin_partition(S, 0, n - 1)


class Solution:

	def palindromicPartition(self, string):
		n = len(string)
		dp = [[-1 for i in range(n)] for j in range(n)]

		def recursive(string, left=0, right=n - 1):
			if left > right:
				return True
			if left == right:
				dp[left][right] = True
				return True
			if dp[left][right] != -1:
				return dp[left][right]
			if string[left] == string[right]:
				dp[left][right] = recursive(string, left + 1, right - 1)
			else:
				dp[left][right] = False
			recursive(string, left + 1, right)
			recursive(string, left, right - 1)
			return dp[left][right]
		recursive(string)
		dp2 = [[-1 for i in range(n)] for j in range(n)]

		def findminimum(string, dp, dp2, left=0, right=0):
			if right == len(string) == left:
				return 0
			if left > right or right >= len(string):
				return float('inf')
			if dp[left][right] != -1:
				return dp[left][right]
			dp[left][right] = findminimum(string, dp, dp2, left, right + 1)
			if dp2[left][right]:
				dp[left][right] = min(dp[left][right], 1 + findminimum(string, dp, dp2, right + 1, right + 1))
			return dp[left][right]
		return findminimum(string, dp2, dp) - 1


from math import *

class Solution:

	def solve(self, i, j, string, dp, grid):
		if grid[i][j]:
			return 0
		if (i, j) in dp:
			return dp[i, j]
		cnt = inf
		for k in range(i, j):
			cnt = min(cnt, 1 + self.solve(i, k, string, dp, grid) + self.solve(k + 1, j, string, dp, grid))
		dp[i, j] = cnt
		return cnt

	def palindromicPartition(self, string):
		n = len(string)
		palindrom_grid = [[0] * n for _ in range(n)]
		for i in range(n):
			for j in range(i, n):
				if i == j:
					palindrom_grid[i][j] = 1
		for i in range(n - 2, -1, -1):
			for j in range(n - 1, i, -1):
				if string[i] == string[j] and (palindrom_grid[i + 1][j - 1] or i + 1 == j):
					palindrom_grid[i][j] = 1
		dp = [inf] * n
		dp[0] = 0
		for j in range(1, n):
			if palindrom_grid[0][j]:
				dp[j] = 0
			else:
				for i in range(j, 0, -1):
					if palindrom_grid[i][j]:
						dp[j] = min(dp[j], 1 + dp[i - 1])
		return dp[-1]
		n = len(string)
		palindrom_grid = [[0] * n for _ in range(n)]
		for i in range(n):
			for j in range(i, n):
				if i == j:
					palindrom_grid[i][j] = 1
		for i in range(n - 2, -1, -1):
			for j in range(n - 1, i, -1):
				if string[i] == string[j] and (palindrom_grid[i + 1][j - 1] or i + 1 == j):
					palindrom_grid[i][j] = 1
		dp = [[inf] * n for _ in range(n)]
		for i in range(n):
			for j in range(i, n):
				if palindrom_grid[i][j]:
					dp[i][j] = 0
				else:
					for k in range(i, j):
						dp[i][j] = min(dp[i][j], 1 + (0 if palindrom_grid[i][k] else dp[i][k]) + (0 if palindrom_grid[k + 1][j] else dp[k + 1][j]))
		return dp[0][-1]
		dp = {}
		n = len(string)
		palindrom_grid = [[0] * n for _ in range(n)]
		for i in range(n):
			for j in range(i, n):
				if i == j:
					palindrom_grid[i][j] = 1
		for i in range(n - 2, -1, -1):
			for j in range(n - 1, i, -1):
				if string[i] == string[j] and (palindrom_grid[i + 1][j - 1] or i + 1 == j):
					palindrom_grid[i][j] = 1
		return self.solve(0, n - 1, string, dp, palindrom_grid)


class Solution:

	def palindromicPartition(self, string):
		mp = {}
		res = self.solve(string, mp)
		return res

	def solve(self, string, mp):
		if len(string) == 0 or string == string[::-1]:
			return 0
		if string in mp:
			return mp[string]
		res = float('inf')
		for i in range(len(string)):
			prefix = string[:i + 1]
			if prefix == prefix[::-1]:
				res = min(res, 1 + self.solve(string[i + 1:], mp))
		mp[string] = res
		return res


class Solution:

	def palindromicPartition(self, string):

		def ispallindrome(s, i, j, dp):
			if i >= j:
				dp[i][j] = 0
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = ispallindrome(s, i + 1, j - 1, dp)
				return dp[i][j]
			return dp[i][j]

		def helper(s, i, j, dp):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if ispallindrome(s, i, j, dp) == 0:
				dp[i][j] = 0
				return dp[i][j]
			ans = float('inf')
			for k in range(i, j):
				if dp[i][k] != -1:
					left = dp[i][k]
				else:
					left = ispallindrome(s, i, k, dp)
					dp[i][k] = left
				if left != 0:
					continue
				if dp[k + 1][j] != -1:
					right = dp[k + 1][j]
				else:
					right = helper(s, k + 1, j, dp)
					dp[k + 1][j] = right
				temp_ans = helper(s, k + 1, j, dp) + 1
				ans = min(ans, temp_ans)
			dp[i][j] = ans
			return dp[i][j]
		dp = [[-1] * len(string) for i in range(len(string))]
		return helper(string, 0, len(string) - 1, dp)