Given string s containing characters as integers only, the task is to delete all characters of this string in a minimum number of steps wherein one step you can delete the substring which is a palindrome. After deleting a substring remaining parts are concatenated.
Example 1:
Input: s = "2553432"
Output: 2
Explanation: In first step remove "55", 
then string becomes "23432" which is a 
palindrome.
Example 2:
Input: s = "1234"
Output: 4
Explanation: Remove each character in 
each step
Your Task:  
You don't need to read input or print anything. Complete the function minStepToDeleteString() which string s as input parameters and returns the integer value
Expected Time Complexity: O(|s|^{3})
Expected Auxiliary Space: O(|s|^{2})
Constraints:
1 ≤ |s| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def minStepToDeleteString(self, s):

		# code here

Solutions:
class Solution:

	def solve(self, s, dp, start, end):
		if start > end:
			return 0
		if start == end:
			return 1
		if dp[start][end] != -1:
			return dp[start][end]
		op1 = op2 = op3 = 1000000000.0
		op1 = 1 + self.solve(s, dp, start + 1, end)
		if s[start] == s[start + 1]:
			op2 = 1 + self.solve(s, dp, start + 2, end)
		for i in range(start + 2, end + 1):
			if s[start] == s[i]:
				op3 = min(op3, self.solve(s, dp, start + 1, i - 1) + self.solve(s, dp, i + 1, end))
		dp[start][end] = min(op1, op2, op3)
		return dp[start][end]

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


class Solution:

	def minStepToDeleteString(self, str):
		N = len(str)
		dp = [[0 for x in range(N + 1)] for y in range(N + 1)]
		for l in range(1, N + 1):
			i = 0
			j = l - 1
			while j < N:
				if l == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + dp[i + 1][j]
					if str[i] == str[i + 1]:
						dp[i][j] = min(1 + dp[i + 2][j], dp[i][j])
					for K in range(i + 2, j + 1):
						if str[i] == str[K]:
							dp[i][j] = min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j])
				i += 1
				j += 1
		return dp[0][N - 1]


import sys
INT_MAX = sys.maxsize

class Solution:

	def min_steps(self, l, r, s, dp):
		if l > r:
			return 0
		if l == r:
			return 1
		if dp[l][r] != -1:
			return dp[l][r]
		(op1, op2, op3) = (INT_MAX, INT_MAX, INT_MAX)
		op1 = 1 + self.min_steps(l + 1, r, s, dp)
		if s[l] == s[l + 1]:
			op2 = 1 + self.min_steps(l + 2, r, s, dp)
		for i in range(l + 2, r + 1):
			if s[l] == s[i]:
				op3 = min(op3, self.min_steps(l + 1, i - 1, s, dp) + self.min_steps(i + 1, r, s, dp))
		dp[l][r] = min(op1, op2, op3)
		return dp[l][r]

	def minStepToDeleteString(self, s):
		n = len(s)
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return self.min_steps(0, n - 1, s, dp)


import sys
INT_MAX = sys.maxsize

class Solution:

	def min_steps(self, i, j, s, dp):
		if i > j:
			return 0
		if i == j:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		min_steps = 1 + self.min_steps(i + 1, j, s, dp)
		if s[i] == s[i + 1]:
			min_steps = 1 + min(min_steps, self.min_steps(i + 2, j, s, dp))
		for k in range(i + 2, j + 1):
			if s[i] == s[k]:
				steps = self.min_steps(i + 1, k - 1, s, dp) + self.min_steps(k + 1, j, s, dp)
				min_steps = min(min_steps, steps)
		dp[i][j] = min_steps
		return dp[i][j]

	def minStepToDeleteString(self, s):
		n = len(s)
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return self.min_steps(0, n - 1, s, dp)


class Solution:

	def minStepToDeleteString(self, s):
		n = len(s)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			dp[i][i] = 1
		j = 1
		while j < n:
			for i in range(n - j):
				dp[i][i + j] = 1 + min(dp[i][i + j - 1], dp[i + 1][i + j])
				for k in range(i + 1, i + j + 1):
					if s[i] == s[k]:
						a = dp[i + 1][k - 1]
						if i + 1 > k - 1:
							a = 1
						b = dp[k + 1][i + j]
						dp[i][i + j] = min(dp[i][i + j], a + b)
			j += 1
		return dp[0][n - 1]


class Solution:

	def minStepToDeleteString(self, s):

		def solve(f, l, d):
			if l < f:
				return 0
			if f == l:
				return 1
			if (f, l) in d:
				return d[f, l]
			(first, second) = (float('inf'), float('inf'))
			first = 1 + solve(f + 1, l, d)
			if s[f] == s[f + 1]:
				second = 1 + solve(f + 2, l, d)
			third = float('inf')
			for i in range(f + 2, l + 1):
				if s[f] == s[i]:
					third = min(third, solve(f + 1, i - 1, d) + solve(i + 1, l, d))
			d[f, l] = min(first, second, third)
			return d[f, l]
		d = {}
		res = solve(0, len(s) - 1, d)
		return res


class Solution:

	def minStepToDeleteString(self, s):
		n = len(s)
		dp = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for l in range(1, n + 1):
			(i, j) = (0, l - 1)
			while j < n:
				if l == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + dp[i + 1][j]
					if s[i] == s[i + 1]:
						dp[i][j] = min(1 + dp[i + 2][j], dp[i][j])
					for k in range(i + 2, j + 1):
						if s[i] == s[k]:
							dp[i][j] = min(dp[i + 1][k - 1] + dp[k + 1][j], dp[i][j])
				i += 1
				j += 1
		return dp[0][n - 1]


import functools

class Solution:

	def minStepToDeleteString(self, s):

		@functools.lru_cache(None)
		def delete_substring(start_idx, end_idx):
			if start_idx == end_idx:
				return 1
			if start_idx > end_idx:
				return 0
			first_case = delete_substring(start_idx + 1, end_idx) + 1
			second_case = float('inf')
			for idx in range(start_idx + 1, end_idx + 1):
				if s[idx] == s[start_idx]:
					if idx == start_idx + 1:
						second_case = min(second_case, delete_substring(start_idx + 2, end_idx)) + 1
					else:
						second_case = min(second_case, delete_substring(start_idx + 1, idx - 1) + delete_substring(idx + 1, end_idx))
			return min(first_case, second_case)
		return delete_substring(0, len(s) - 1)


class Solution:

	def minStepToDeleteString(self, str):
		N = len(str)
		dp = [[0 for x in range(N + 1)] for y in range(N + 1)]
		for l in range(1, N + 1):
			i = 0
			j = l - 1
			while j < N:
				if l == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + dp[i + 1][j]
					if str[i] == str[i + 1]:
						dp[i][j] = min(1 + dp[i + 2][j], dp[i][j])
					for K in range(i + 2, j + 1):
						if str[i] == str[K]:
							dp[i][j] = min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j])
				i += 1
				j += 1
		return dp[0][N - 1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.minStepToDeleteString(s)
		print(ans)


class Solution:

	def minStepToDeleteString(self, s):
		N = len(s)
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for gap in range(1, N + 1):
			i = 0
			j = gap - 1
			while j < N:
				if gap == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + dp[i + 1][j]
					if s[i] == s[i + 1]:
						dp[i][j] = min(1 + dp[i + 2][j], dp[i][j])
					for K in range(i + 2, j + 1):
						if s[i] == s[K]:
							dp[i][j] = min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j])
				i += 1
				j += 1
		return dp[0][N - 1]


class Solution:

	def minStepToDeleteString(self, s):
		cache = {}

		def dp(i, j):
			if (i, j) in cache:
				return cache[i, j]
			if i > j:
				cache[i, j] = 0
				return cache[i, j]
			if i == j:
				cache[i, j] = 1
				return cache[i, j]
			cache[i, j] = float('inf')
			for k in range(i, j + 1):
				if s[i] == s[k]:
					temp = 1 + dp(k + 1, j) if k - i <= 1 else dp(i + 1, k - 1) + dp(k + 1, j)
					cache[i, j] = min(cache[i, j], temp)
			return cache[i, j]
		return dp(0, len(s) - 1)


class Solution:

	def minStepToDeleteString(self, s):
		length = len(s)
		if length < 1:
			return 0
		if length < 2:
			return 1
		lookup_min_steps = [[0] * length for i in range(length)]
		for i in range(length):
			lookup_min_steps[i][i] = 1
		for len_str in range(2, length + 1):
			for i in range(0, length - len_str + 1):
				j = i + len_str - 1
				min_steps = length
				min_steps = min(min_steps, lookup_min_steps[i][j - 1] + 1)
				for k in range(i, j):
					if s[k] == s[j]:
						if k == j - 1:
							min_steps = min(min_steps, lookup_min_steps[i][k - 1] + 1)
						else:
							min_steps = min(min_steps, lookup_min_steps[i][k - 1] + lookup_min_steps[k + 1][j - 1])
				lookup_min_steps[i][j] = min_steps
		return lookup_min_steps[0][length - 1]


class Solution:

	def minStepToDeleteString(self, str1):
		n = len(str1)
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		for l in range(1, n + 1):
			i = 0
			j = l - 1
			while j < n:
				if l == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + dp[i + 1][j]
					if str1[i] == str1[i + 1]:
						dp[i][j] = min(1 + dp[i + 2][j], dp[i][j])
					for K in range(i + 2, j + 1):
						if str1[i] == str1[K]:
							dp[i][j] = min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j])
				i += 1
				j += 1
		return dp[0][n - 1]