Given a String, find the longest palindromic subsequence.
Example 1:
Input:
S = "bbabcbcab"
Output: 7
Explanation: Subsequence "babcbab" is the
longest subsequence which is also a palindrome.
Example 2:
Input: 
S = "abcd"
Output: 1
Explanation: "a", "b", "c" and "d" are
palindromic and all have a length 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestPalinSubseq() which takes the string S as input and returns an integer denoting the length of the longest palindromic subsequence of S.
Expected Time Complexity: O(|S|*|S|).
Expected Auxiliary Space: O(|S|*|S|).
Constraints:
1 ≤ |S| ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:



    def longestPalinSubseq(self, S):

        # code here

Solutions:
class Solution:

	def longestPalinSubseq(self, s):
		rs = s[::-1]
		n = len(s)
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s[i - 1] == rs[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][n]


import sys

class Solution:

	def longestPalinSubseq(self, string: str) -> int:
		dp = [None] * (len(string) + 1)
		(dp[0], dp[1]) = ([None, None, None], [0, None, None])
		for i in range(1, len(string)):
			for j in range(len(dp) - 3, -1, -1):
				if dp[j] is None:
					continue
				start = dp[j][0] - 1 if j != 0 else i - 1
				stop = dp[j + 2][0] if dp[j + 2] is not None else -1
				for k in range(start, stop, -1):
					if string[i] == string[k]:
						dp[j + 2] = [k, i, dp[j]]
						break
			dp[1] = [i, None, None]
		for i in range(len(dp) - 1, -1, -1):
			if dp[i] is not None:
				ans = i
				break
		dpData = dp[ans]
		ansLeft = []
		ansRight = []
		while dpData is not None:
			if dpData[0] is not None:
				ansLeft.append(dpData[0])
			if dpData[1] is not None:
				ansRight.append(dpData[1])
			dpData = dpData[2]
		ansStringIndexes = ansLeft + ansRight[::-1]
		ansString = ''.join([string[i] for i in ansStringIndexes])
		return ans


class Solution:

	def longestPalinSubseq(self, S):

		def lcs(x, y, s1, s2):
			l = [[0] * (y + 1) for j in range(x + 1)]
			for i in range(x + 1):
				for j in range(y + 1):
					if i == 0 or j == 0:
						l[i][j] = 0
					elif s1[i - 1] == s2[j - 1]:
						l[i][j] = l[i - 1][j - 1] + 1
					else:
						l[i][j] = max(l[i - 1][j], l[i][j - 1])
			return l[x][y]
		S1 = S[::-1]
		ans = lcs(len(S), len(S1), S, S1)
		return ans


class Solution:

	def lcs(self, str1, str2):
		lcsMatrix = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
		for x in range(len(str1) + 1):
			for y in range(len(str2) + 1):
				if x == 0 or y == 0:
					lcsMatrix[x][y] = 0
				elif str1[x - 1] == str2[y - 1]:
					lcsMatrix[x][y] = 1 + lcsMatrix[x - 1][y - 1]
				else:
					lcsMatrix[x][y] = max(lcsMatrix[x - 1][y], lcsMatrix[x][y - 1])
		return lcsMatrix[len(str1)][len(str2)]

	def longestPalinSubseq(self, S):
		return self.lcs(S, S[::-1])


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

class Solution:

	def longestPalinSubseq(self, S):
		dp = {}

		def f(i, j):
			if (i, j) in dp:
				return dp[i, j]
			if i > j:
				return 0
			if i == j:
				return 1
			if S[i] == S[j]:
				dp[i, j] = 2 + f(i + 1, j - 1)
			else:
				dp[i, j] = max(f(i + 1, j), f(i, j - 1))
			return dp[i, j]
		return f(0, len(S) - 1)


class Solution:

	def longestPalinSubseq(self, text1: str):
		text2 = text1[::-1]
		next = [0 for col in range(len(text2) + 1)]
		for i in range(len(text1) - 1, -1, -1):
			curr = [0 for row in range(len(text2) + 1)]
			for j in range(len(text2) - 1, -1, -1):
				ans = 0
				if text1[i] == text2[j]:
					ans = 1 + next[j + 1]
				else:
					ans = max(next[j], curr[j + 1])
				curr[j] = ans
			next = curr
		return next[0]


class Solution:

	def solveTab(self, a, b):
		dp = [[0 for col in range(len(b) + 1)] for row in range(len(a) + 1)]
		for i in range(len(a) - 1, -1, -1):
			for j in range(len(b) - 1, -1, -1):
				ans = 0
				if a[i] == b[j]:
					ans = 1 + dp[i + 1][j + 1]
				else:
					ans = max(dp[i + 1][j], dp[i][j + 1])
				dp[i][j] = ans
		return dp[0][0]

	def longestPalinSubseq(self, text1):
		text2 = text1[::-1]
		return self.solveTab(text1, text2)


class Solution:

	def longestPalinSubseq(self, s1):
		x = len(s1)
		y = x
		s2 = s1[::-1]
		dp = [[-1 for i in range(y)] for j in range(x)]

		def answer(i, j, s1, s2):
			if i == -1 or j == -1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				dp[i][j] = 1 + answer(i - 1, j - 1, s1, s2)
				return dp[i][j]
			else:
				dp[i][j] = max(answer(i, j - 1, s1, s2), answer(i - 1, j, s1, s2))
				return dp[i][j]
		return answer(x - 1, y - 1, s1, s2)


import numpy as np

class Solution:

	def rec_sol(self, S, start, end, dp):
		if start == end:
			return 1
		if start > end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		if S[start] == S[end]:
			ans = 2 + self.rec_sol(S, start + 1, end - 1, dp)
		else:
			ans = max(self.rec_sol(S, start, end - 1, dp), self.rec_sol(S, start + 1, end, dp))
		dp[start][end] = ans
		return ans

	def dp_sol(self, S):
		len_s = len(S)
		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] = 1
				elif S[j] == S[i]:
					dp[j][i] = 2 + dp[j + 1][i - 1]
				else:
					dp[j][i] = max(dp[j + 1][i], dp[j][i - 1])
		return dp[0][len_s - 1]

	def longestPalinSubseq(self, S):
		return self.dp_sol(S)


import numpy as np

class Solution:

	def rec_sol(self, S, start, end, dp):
		if start == end:
			return 1
		if start > end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		if S[start] == S[end]:
			ans = 2 + self.rec_sol(S, start + 1, end - 1, dp)
		else:
			ans = max(self.rec_sol(S, start, end - 1, dp), self.rec_sol(S, start + 1, end, dp))
		dp[start][end] = ans
		return ans

	def longestPalinSubseq(self, S):
		len_s = len(S)
		dp = np.array([[-1] * len_s] * len_s)
		return self.rec_sol(S, 0, len_s - 1, dp)


class Solution:

	def longestPalinSubseq(self, S):
		s2 = S[::-1]
		x = len(S)
		y = len(s2)
		T = [[0 for i in range(y + 1)] for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					T[i][j] = 0
				elif S[i - 1] == s2[j - 1]:
					T[i][j] = 1 + T[i - 1][j - 1]
				else:
					T[i][j] = max(T[i - 1][j], T[i][j - 1])
		return T[x][y]


class Solution:

	def lcs(self, s1, s2, x, y):
		t = [[-1 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		return t[x][y]

	def longestPalinSubseq(self, S):
		x = len(S)
		return self.lcs(S, S[::-1], x, x)


class Solution:

	def longestPalinSubseq(self, S):
		reversedS = S[::-1]
		N = len(S)
		stateMap = [[0 for _ in range(N + 1)] for i in range(N + 1)]
		for r in range(1, N + 1):
			for c in range(1, N + 1):
				if S[r - 1] == reversedS[c - 1]:
					stateMap[r][c] = 1 + stateMap[r - 1][c - 1]
				else:
					stateMap[r][c] = max(stateMap[r - 1][c], stateMap[r][c - 1])
		return stateMap[N][N]


class Solution:

	def longestPalinSubseq(self, S):
		rev = S[::-1]
		ans = self.lcs(len(S), len(rev), S, rev)
		return ans

	def lcs(self, x, y, s1, s2):
		dp = [[0 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
		return dp[x][y]


class Solution:

	def longestPalinSubseq(self, Str):
		tmp = Str[::-1]
		n = len(Str)
		dp = [[0] * (n + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if Str[i - 1] == tmp[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		temp = ''
		for i in range(n - 1, -1, -1):
			temp += S[i]
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif S[i - 1] == temp[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = 0
		for i in range(n + 1):
			for j in range(n + 1):
				ans = max(ans, dp[i][j])
		return ans


class Solution:

	def longestPalinSubseq(self, S):
		X = S
		Y = S[::-1]
		(m, n) = (len(X), len(Y))
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[i][j]


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		m = len(S)
		S2 = S[::-1]
		x = self.lcs(n, m, S, S2)
		return x

	def lcs(self, x, y, s1, s2):
		t = [[-1 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(y + 1):
			t[0][i] = 0
		for j in range(x + 1):
			t[j][0] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[x][y]


class Solution:

	def ls(self, x, y, s1, s2, dp):
		if x == 0 or y == 0:
			return 0
		if dp[x][y] != -1:
			return dp[x][y]
		if s1[x - 1] == s2[y - 1]:
			dp[x][y] = 1 + self.ls(x - 1, y - 1, s1, s2, dp)
			return dp[x][y]
		else:
			dp[x][y] = max(self.ls(x - 1, y, s1, s2, dp), self.ls(x, y - 1, s1, s2, dp))
			return dp[x][y]

	def longestPalinSubseq(self, S):
		S1 = S
		S2 = S1[::-1]
		m = len(S1)
		n = len(S2)
		dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
		return self.ls(m, n, S1, S2, dp)


class Solution:

	def longestPalinSubseq(self, S):
		s1 = S[::-1]
		n = len(S)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == S[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[n][n]


class Solution:

	def solve(self, x, y, s1, s2, i, j):
		if i == x or j == y:
			return 0
		if s1[i] == s2[j]:
			return 1 + self.solve(x, y, s1, s2, i + 1, j + 1)
		else:
			return max(self.solve(x, y, s1, s2, i + 1, j), self.solve(x, y, s1, s2, i, j + 1))

	def solve_memo(self, x, y, s1, s2, i, j, F):
		if i == x or j == y:
			return 0
		if F[i][j] != -1:
			return F[i][j]
		if s1[i] == s2[j]:
			F[i][j] = 1 + self.solve_memo(x, y, s1, s2, i + 1, j + 1, F)
		else:
			F[i][j] = max(self.solve_memo(x, y, s1, s2, i + 1, j, F), self.solve_memo(x, y, s1, s2, i, j + 1, F))
		return F[i][j]

	def solve_tab(self, x, y, s1, s2):
		F = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				if s1[i] == s2[j]:
					F[i][j] = 1 + F[i + 1][j + 1]
				else:
					F[i][j] = max(F[i + 1][j], F[i][j + 1])
		return F[0][0]

	def solve_tab2(self, x, y, s1, s2):
		curr = [0 for _ in range(y + 1)]
		nextt = [0 for _ in range(y + 1)]
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				if s1[i] == s2[j]:
					curr[j] = 1 + nextt[j + 1]
				else:
					curr[j] = max(nextt[j], curr[j + 1])
			nextt = curr[:]
		return nextt[0]

	def longestPalinSubseq(self, S):
		rev_s = S[::-1]
		(x, y) = (len(S), len(rev_s))
		F = [[-1 for _ in range(y)] for _ in range(x)]
		return self.solve_memo(x, y, S, rev_s, 0, 0, F)


class Solution:

	def longestPalinSubseq(self, s):
		n = len(s)
		str1 = s
		str2 = s[::-1]
		res = ''
		l = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for i in range(n):
			for j in range(n):
				if str1[i] == str2[j]:
					l[i + 1][j + 1] = 1 + l[i][j]
				else:
					l[i + 1][j + 1] = max(l[i][j + 1], l[i + 1][j])
		return l[-1][-1]


class Solution:

	def longestPalinSubseq(self, s):
		s1 = s[::-1]
		x = len(s)
		y = len(s)
		dp = [[0 for i in range(x + 1)] for j in range(y + 1)]
		for i in range(1, y + 1):
			for j in range(1, x + 1):
				if s[i - 1] == s1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[y][x]


class Solution:

	def longestPalinSubseq(self, s):
		s1 = s
		s2 = s[::-1]
		n = len(s1)
		m = len(s2)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:
	dp = []

	def gen(self, s, l, r, c, flag):
		if l == r:
			return 1
		if r - l == 1 and s[l] != s[r]:
			return 1
		if l > r:
			return 0
		if self.dp[l][r] != -1:
			return self.dp[l][r]
		if s[l] == s[r]:
			c = self.gen(s, l + 1, r - 1, c, flag) + 2
		p = self.gen(s, l + 1, r, 0, flag)
		q = self.gen(s, l, r - 1, 0, flag)
		self.dp[l][r] = max(p, q, c)
		return max(p, q, c)

	def longestPalinSubseq(self, S):
		l = len(S)
		self.dp = []
		for i in range(l + 1):
			b = []
			for j in range(l + 1):
				b.append(-1)
			self.dp.append(b)
		a = self.gen(S, 0, len(S) - 1, 0, 0)
		return a


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def longestPalinSubseq(self, S):
		d = dict()

		def dfs(i, j):
			if i > j:
				return 0
			if i == j:
				return 1
			if d.get((i, j)) != None:
				return d[i, j]
			if S[i] == S[j]:
				d[i, j] = 2 + dfs(i + 1, j - 1)
				return d[i, j]
			d[i, j] = max(dfs(i + 1, j), dfs(i, j - 1))
			return d[i, j]
		return dfs(0, len(S) - 1)


class Solution:

	def longestPalinSubseq(self, S):
		dp = [[0 for j in range(len(S))] for i in range(len(S))]
		for k in range(len(S)):
			j = k
			for i in range(len(S) - k):
				if i == j:
					dp[i][j] = 1
					j += 1
					continue
				if s[i] == s[j]:
					dp[i][j] = 2 + dp[i + 1][j - 1]
					j += 1
					continue
				dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
				j += 1
		return dp[0][-1]


class Solution:

	def longestPalinSubseq(self, S):
		st1 = S
		st2 = S[::-1]
		m = len(st1)
		n = len(st2)
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if st1[i - 1] == st2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		length = dp[m][n]
		return length


class Solution:

	def longestPalinSubseq(self, S):
		if len(S) == 0:
			return 0
		dp = [[-1 for _ in range(len(S))] for __ in range(len(S))]
		return self.is_same(S, dp, 0, len(S) - 1)

	def is_same(self, string, arr, start, end):
		if start == end:
			return 1
		if start > end:
			return 0
		if arr[start][end] != -1:
			return arr[start][end]
		if string[start] == string[end]:
			arr[start][end] = self.is_same(string, arr, start + 1, end - 1) + 2
		else:
			arr[start][end] = max(self.is_same(string, arr, start, end - 1), self.is_same(string, arr, start + 1, end))
		return arr[start][end]


class Solution:

	def longestPalinSubseq(self, s):
		dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
		for k in range(1, len(s) + 1):
			for i in range(len(s) - k + 1):
				j = k + i - 1
				if i == j:
					dp[i][j] = 1
				elif i + 1 == j and s[i] == s[j]:
					dp[i][j] = 2
				elif s[i] == s[j]:
					dp[i][j] = dp[i + 1][j - 1] + 2
				else:
					dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
		return dp[0][-1]


class Solution:

	def longestPalinSubseq(self, S):
		self.memo = [[0 for _ in range(len(s))] for _ in range(len(s))]
		return self.get_longest(0, len(S) - 1, S)

	def get_longest(self, i, j, S):
		if i == j:
			return 1
		if i > j:
			return 0
		if self.memo[i][j] != 0:
			return self.memo[i][j]
		if s[i] == s[j]:
			self.memo[i][j] = 2 + self.get_longest(i + 1, j - 1, S)
		else:
			self.memo[i][j] = max(self.get_longest(i + 1, j, S), self.get_longest(i, j - 1, S))
		return self.memo[i][j]


class Solution:

	def longestPalinSubseq(self, s):
		dp = {}

		def f(i, j, s1, s2):
			if i < 0 or j < 0:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			if s1[i] == s2[j]:
				return 1 + f(i - 1, j - 1, s1, s2)
			dp[i, j] = max(f(i - 1, j, s1, s2), f(i, j - 1, s1, s2))
			return dp[i, j]
		n = len(s)
		return f(n - 1, n - 1, s, s[::-1])


class Solution:

	def longestPalinSubseq(self, S):
		Srev = S[::-1]
		dp = [[0 for j in range(len(Srev) + 1)] for i in range(len(S) + 1)]
		for i in range(1, len(dp)):
			for j in range(1, len(dp[0])):
				s1_sub = S[:i]
				s2_sub = Srev[:j]
				if s1_sub[-1] == s2_sub[-1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		dp = [[0 for _ in range(n)] for _ in range(n)]
		max_len = 0
		for i in range(n):
			dp[i][i] = 1
			if i and S[i] == S[i - 1]:
				dp[i - 1][i] = 2
			else:
				dp[i - 1][i] = 1
		for l in range(3, n + 1):
			for j in range(0, n - l + 1):
				if S[j] == S[j + l - 1]:
					dp[j][j + l - 1] = dp[j + 1][j + l - 2] + 2
				else:
					dp[j][j + l - 1] = max(dp[j + 1][j + l - 1], dp[j][j + l - 2])
		return dp[0][n - 1]


class Solution:

	def longestPalinSubseq(self, S):

		def lps(s, left, right, dp):
			key = (left, right)
			if left > right:
				return 0
			if left == right:
				return 1
			if key in dp:
				return dp[key]
			if s[left] == s[right]:
				dp[key] = 2 + lps(s, left + 1, right - 1, dp)
				return dp[key]
			else:
				dp[key] = max(lps(s, left + 1, right, dp), lps(s, left, right - 1, dp))
				return dp[key]
		dp = dict()
		res = lps(S, 0, len(S) - 1, dp)
		return res


class Solution:

	def longestPalinSubseq(self, S):
		n = len(s)
		dp = [[-1] * n for i in range(n)]

		def lcs(i, j, n, s1, s2):
			if i >= n or j >= n:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			inc = 0
			if s1[i] == s2[j]:
				inc = 1 + lcs(i + 1, j + 1, n, s1, s2)
			inc = max(inc, lcs(i + 1, j, n, s1, s2))
			inc = max(inc, lcs(i, j + 1, n, s1, s2))
			dp[i][j] = inc
			return inc
		return lcs(0, 0, n, s, s[::-1])


class Solution:

	def longestPalinSubseq(self, s):
		s1 = s
		s2 = s[::-1]
		x = len(s1)
		y = len(s2)
		dp = [[0] * (y + 1) for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				(m, n) = (i, j)
				if m == 0 or n == 0:
					pass
				elif s1[m - 1] == s2[n - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					c1 = dp[i - 1][j]
					c2 = dp[i][j - 1]
					dp[i][j] = max(c1, c2)
		return dp[x][y]


class Solution:

	def longestPalinSubseq(self, S):
		lps = [[0 for i in range(len(S))] for j in range(len(S))]
		for gap in range(0, len(S)):
			j = gap
			i = 0
			while i < len(S) and j < len(S):
				if gap == 0:
					lps[i][j] = 1
				elif gap == 1:
					if S[i] == S[j]:
						lps[i][j] = 2
					else:
						lps[i][j] = 1
				elif S[i] == S[j]:
					lps[i][j] = lps[i + 1][j - 1] + 2
				else:
					lps[i][j] = max(lps[i][j - 1], lps[i + 1][j])
				j += 1
				i += 1
		return lps[0][len(S) - 1]


class Solution:

	def longestPalinSubseq(self, S):

		def lcs(x, y, m, n):
			dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
			for i in range(0, m):
				for j in range(0, n):
					if i == 0 or j == 0:
						dp[i][j] = 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					if x[i - 1] == y[j - 1]:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			return dp[m][n]
		S1 = S[::-1]
		n = len(S)
		m = len(S1)
		y = lcs(S, S1, n, m)
		return y


class Solution:

	def longestPalinSubseq(self, S):
		n = len(s)
		(curr, prev) = ([0] * n, [0] * n)
		for i in range(n - 1, -1, -1):
			curr[i] = 1
			for j in range(i + 1, n):
				if s[i] == s[j]:
					curr[j] = prev[j - 1] + 2
				else:
					curr[j] = max(prev[j], curr[j - 1])
			(curr, prev) = (prev, curr)
		return prev[n - 1]


class Solution:

	def __init__(self):
		self.res = ''
		self.leng = 0

	def longestPalinSubseq(self, s1):

		def lcs(i1, i2, n1, n2, s1, s2, dp, s):
			if i1 >= n1 or i2 >= n2:
				return 0
			if dp[i1][i2] != -1:
				return dp[i1][i2]
			m1 = -10 ** 9
			m2 = -10 ** 9
			if s1[i1] == s2[i2]:
				return lcs(i1 + 1, i2 + 1, n1, n2, s1, s2, dp, s + s1[i1]) + 1
			else:
				m1 = lcs(i1 + 1, i2, n1, n2, s1, s2, dp, '')
				m2 = lcs(i1, i2 + 1, n1, n2, s1, s2, dp, '')
			dp[i1][i2] = max(m1, m2)
			return dp[i1][i2]
		n1 = len(s1)
		s2 = s1[::-1]
		dp = []
		for i in range(n1):
			dp.append([-1] * n1)
		return lcs(0, 0, n1, n1, s1, s2, dp, '')


class Solution:

	def longestPalinSubseq(self, S):
		s = S
		dp = [[1] * len(S) for i in range(len(S))]
		for i in range(len(S) - 1):
			if s[i] == s[i + 1]:
				dp[i][i + 1] = 2
			else:
				dp[i][i + 1] = 1
		for l in range(3, len(S) + 1):
			for i in range(len(S)):
				j = i + l - 1
				if j >= len(S):
					continue
				if s[i] == s[j]:
					dp[i][j] = max(dp[i + 1][j - 1] + 2, dp[i][j])
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1], dp[i][j])
		return dp[0][len(S) - 1]


class Solution:

	def longestPalinSubseq(self, S):
		s = S[::-1]
		m = len(S)
		n = len(s)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		ma = dp[0][0]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				x = i
				y = j
				if m == 0 or n == 0:
					dp[i][j] = 0
				elif S[x - 1] == s[y - 1]:
					dp[i][j] = 1 + dp[x - 1][y - 1]
				else:
					dp[i][j] = max(dp[x - 1][y], dp[x][y - 1])
		return dp[m][n]


class Solution:

	def solve(self, S, i, j, dp):
		if i == j:
			dp[i][j] = 1
			return 1
		if i + 1 == j and S[i] == S[j]:
			dp[i][j] = 2
			return 2
		if dp[i][j] != -1:
			return dp[i][j]
		if S[i] == S[j]:
			dp[i][j] = self.solve(S, i + 1, j - 1, dp) + 2
		else:
			dp[i][j] = max(self.solve(S, i + 1, j, dp), self.solve(S, i, j - 1, dp))
		return dp[i][j]

	def longestPalinSubseq(self, S):
		dp = [[-1 for each in range(len(S) + 1)] for each1 in range(len(S) + 1)]
		a = self.solve(S, 0, len(S) - 1, dp)
		return a


class Solution:

	def longestPalinSubseq(self, S):
		arr = [[0 for a in range(len(S) + 1)] for b in range(len(S) + 1)]
		st1 = S[::-1]
		for i in range(len(S)):
			for j in range(len(S)):
				if st1[j] == S[i]:
					arr[i + 1][j + 1] = 1 + arr[i][j]
				else:
					arr[i + 1][j + 1] = max(arr[i + 1][j], arr[i][j + 1])
		return arr[-1][-1]


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		t = [[-1 for i in range(n + 1)] for _ in range(n + 1)]

		def rever(S):
			a = list(S)
			a = a[::-1]
			return ''.join(a)

		def lcs(x, y, n, m):
			for i in range(n + 1):
				for j in range(m + 1):
					if i == 0 or j == 0:
						t[i][j] = 0
			for i in range(1, n + 1):
				for j in range(1, m + 1):
					if x[i - 1] == y[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
					else:
						t[i][j] = max(t[i - 1][j], t[i][j - 1])
			return t[n][m]
		s1 = rever(S)
		return lcs(S, s1, n, n)


class Solution:

	def f(self, s1, s2, ind1, ind2, dp):
		if ind1 < 0 or ind2 < 0:
			return 0
		if dp[ind1][ind2] != -1:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			dp[ind1][ind2] = 1 + self.f(s1, s2, ind1 - 1, ind2 - 1, dp)
			return dp[ind1][ind2]
		dp[ind1][ind2] = 0 + max(self.f(s1, s2, ind1, ind2 - 1, dp), self.f(s1, s2, ind1 - 1, ind2, dp))
		return dp[ind1][ind2]

	def longestPalinSubseq(self, S):
		x = len(S)
		dp = [[-1 for i in range(x)] for j in range(x)]
		s2 = S[::-1]
		return self.f(S, s2, x - 1, x - 1, dp)


class Solution:

	def longestPalinSubseq(self, S):
		n = len(s)
		memo = [[-1 for _ in range(n)] for _ in range(n)]

		def solve(l, r, memo):
			if l >= n or r < 0:
				return 0
			if memo[l][r] != -1:
				return memo[l][r]
			if s[l] == s[r]:
				memo[l][r] = 1 + solve(l + 1, r - 1, memo)
				return memo[l][r]
			memo[l][r] = max(solve(l, r - 1, memo), solve(l + 1, r, memo))
			return memo[l][r]
		ans = solve(0, n - 1, memo)
		return ans


class Solution:

	def LPS(self, string, i, j, dp):
		if i > len(string) - 1 or j < 0 or i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if i == j:
			return 1
		if string[i] == string[j]:
			ans = 2 + self.LPS(string, i + 1, j - 1, dp)
		else:
			left = self.LPS(string, i + 1, j, dp)
			right = self.LPS(string, i, j - 1, dp)
			ans = max(left, right)
		dp[i][j] = ans
		return ans

	def longestPalinSubseq(self, S):
		string = S
		n = len(string)
		dp = [[-1 for i in range(n)] for j in range(n)]
		return self.LPS(string, 0, n - 1, dp)


class Solution:

	def longestPalinSubseq(self, str):
		n = len(str)
		L = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			L[i][i] = 1
		for cl in range(2, n + 1):
			for i in range(n - cl + 1):
				j = i + cl - 1
				if str[i] == str[j] and cl == 2:
					L[i][j] = 2
				elif str[i] == str[j]:
					L[i][j] = L[i + 1][j - 1] + 2
				else:
					L[i][j] = max(L[i][j - 1], L[i + 1][j])
		return L[0][n - 1]


class Solution:

	def longestPalinSubseq(self, S):
		s1 = S[::-1]
		n = len(S)
		res = [[0 for _ in range(n + 1)] for x in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if S[i - 1] == s1[j - 1]:
					res[i][j] = 1 + res[i - 1][j - 1]
				else:
					res[i][j] = max(res[i - 1][j], res[i][j - 1])
		return res[n][n]


class Solution:

	def longestPalinSubseq(self, S):
		b = S[::-1]
		r = len(S)
		c = len(b)
		dp = [[0 for i in range(c + 1)] for i in range(r + 1)]
		for i in range(1, r + 1):
			for j in range(1, c + 1):
				if S[i - 1] == b[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def longestPalinSubseq(self, S):

		def reverse(s):
			str = ''
			for i in s:
				str = i + str
			return str

		def lcs(x, y, s1, s2):
			T = [[0] * (y + 1) for i in range(x + 1)]
			for i in range(1, x + 1):
				for j in range(1, y + 1):
					if s1[i - 1] == s2[j - 1]:
						T[i][j] = 1 + T[i - 1][j - 1]
					else:
						T[i][j] = max(T[i - 1][j], T[i][j - 1])
			return T[x][y]
		return lcs(len(S), len(S), S, reverse(S))


def lcs(X, Y, m, n, dp):
	if m == 0 or n == 0:
		return 0
	if dp[m][n] != -1:
		return dp[m][n]
	if X[m - 1] == Y[n - 1]:
		dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp)
		return dp[m][n]
	else:
		dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp))
		return dp[m][n]

class Solution:

	def longestPalinSubseq(self, S):
		s2 = S
		s2 = s2[::-1]
		n = len(S)
		dp = [[-1 for i in range(n + 1)] for i in range(n + 1)]
		return lcs(s2, S, n, n, dp)


class Solution:

	def longestPalinSubseq(self, s1):
		s2 = s1[::-1]
		(n, m) = (len(s1), len(s2))
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i1 in range(1, n + 1):
			for i2 in range(1, m + 1):
				if s1[i1 - 1] == s2[i2 - 1]:
					dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]
				else:
					dp[i1][i2] = 0 + max(dp[i1 - 1][i2], dp[i1][i2 - 1])
		return dp[n][m]


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		self.d = [[None] * n for i in range(n)]
		self.solve(S, S[::-1], 0, 0, len(S))
		return self.d[0][0]

	def solve(self, s, r, i, j, n):
		if i == n or j == n:
			return 0
		if self.d[i][j] is not None:
			return self.d[i][j]
		if s[i] == r[j]:
			self.d[i][j] = 1 + self.solve(s, r, i + 1, j + 1, n)
		else:
			self.d[i][j] = max(self.solve(s, r, i + 1, j, n), self.solve(s, r, i, j + 1, n))
		return self.d[i][j]


class Solution:

	def longestPalinSubseq(self, S):

		def manu(s1, s2, i, j):
			if i == len(s1) or j == len(s1):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				k = 1 + manu(s1, s2, i + 1, j + 1)
			else:
				k = max(manu(s1, s2, i + 1, j), manu(s1, s2, i, j + 1))
			dp[i][j] = k
			return k
		dp = [[-1 for i in range(len(s))] for i in range(len(s))]
		return manu(s, s[::-1], 0, 0)


class Solution:

	def f(self, i, j, n, s, s1, dp):
		if i == n or j == n:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		ans = 0
		if s[i] == s1[j]:
			ans = 1 + self.f(i + 1, j + 1, n, s, s1, dp)
		else:
			ans = max(self.f(i + 1, j, n, s, s1, dp), self.f(i, j + 1, n, s, s1, dp))
		dp[i][j] = ans
		return ans

	def longestPalinSubseq(self, S):
		s1 = s[::-1]
		dp = [[-1 for i in range(len(s1))] for j in range(len(S))]
		return self.f(0, 0, len(S), S, s1, dp)


class Solution:

	def longestPalinSubseq(self, S):
		n = len(S)
		t = [[0] * (n + 1) for _ in range(n + 2)]
		S1 = S[::-1]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if S[i - 1] == S1[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[n][n]


class Solution:

	def pali(self, s, l, r):
		if (l, r) in self.d:
			return self.d[l, r]
		if l == r:
			self.d[l, r] = 1
			return self.d[l, r]
		if l + 1 == r and s[l] == s[r]:
			self.d[l, r] = 2
			return self.d[l, r]
		if s[l] == s[r]:
			self.d[l, r] = self.pali(s, l + 1, r - 1) + 2
			return self.d[l, r]
		self.d[l, r] = max(self.pali(s, l + 1, r), self.pali(s, l, r - 1))
		return self.d[l, r]

	def longestPalinSubseq(self, S):
		self.ans = ''
		self.d = {}
		return self.pali(S, 0, len(S) - 1)


class Solution:

	def longestPalinSubseq(self, a):
		n = len(a)
		b = a[::-1]

		def fun(i, j):
			if i == 0 or j == 0:
				return int(a[i] == b[j])
			if a[i] == b[j]:
				return 1 + fun(i - 1, j - 1)
			return max(fun(i, j - 1), fun(i - 1, j))
		dp = [[0] * (n + 1) for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if a[i - 1] == b[j - 1]:
					dp[i][j] += 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[n][n]


class Solution:

	def longestPalinSubseq(self, S):
		s = S
		s2 = s[::-1]
		n = len(s)
		dp = [[-1 for i in range(n)] for i in range(n)]

		def f(ind1, ind2, dp):
			if ind1 < 0 or ind2 < 0:
				return 0
			if dp[ind1][ind2] != -1:
				return dp[ind1][ind2]
			if s[ind1] == s2[ind2]:
				dp[ind1][ind2] = 1 + f(ind1 - 1, ind2 - 1, dp)
				return dp[ind1][ind2]
			dp[ind1][ind2] = max(f(ind1 - 1, ind2, dp), f(ind1, ind2 - 1, dp))
			return dp[ind1][ind2]
		return f(n - 1, n - 1, dp)


class Solution:

	def longestPalinSubseq(self, S):
		l = len(S)
		dp = [[0 for i in range(l)] for j in range(l)]
		for i in range(l):
			dp[i][i] = 1
		for ls in range(2, l + 1):
			for i in range(l - ls + 1):
				j = i + ls - 1
				if S[i] == S[j] and ls == 2:
					dp[i][j] = 2
				elif S[i] == S[j]:
					dp[i][j] = 2 + dp[i + 1][j - 1]
				else:
					dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
		return dp[0][l - 1]


class Solution:

	def longestPalinSubseq(self, s):
		s1 = s
		s2 = s1[::-1]
		dp = [[-1 for i in range(len(s2))] for j in range(len(s1))]
		return self.helper(0, 0, s1, s2, dp)

	def helper(self, i, j, s1, s2, dp):
		if i == len(s1) or j == len(s2):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s1[i] == s2[j]:
			dp[i][j] = 1 + self.helper(i + 1, j + 1, s1, s2, dp)
			return dp[i][j]
		else:
			dp[i][j] = max(self.helper(i + 1, j, s1, s2, dp), self.helper(i, j + 1, s1, s2, dp))
			return dp[i][j]


class Solution:

	def find_lcs(self, dp, str1, str2, m, n):
		if m == 0 or n == 0:
			return 0
		if dp[m][n] != -1:
			return dp[m][n]
		if str1[m - 1] == str2[n - 1]:
			dp[m][n] = 1 + self.find_lcs(dp, str1, str2, m - 1, n - 1)
			return dp[m][n]
		else:
			dp[m][n] = max(self.find_lcs(dp, str1, str2, m - 1, n), self.find_lcs(dp, str1, str2, m, n - 1))
			return dp[m][n]

	def longestPalinSubseq(self, S):
		m = len(S)
		dp = [[-1 for i in range(m + 1)] for j in range(m + 1)]
		return self.find_lcs(dp, S, S[::-1], m, m)


class Solution:

	def solve(self, S1, S2, m, n, dp):
		if m == 0 or n == 0:
			return 0
		ct = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					ct = max(ct, dp[i][j])
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
					ct = max(ct, dp[i][j])
		return ct

	def longestPalinSubseq(self, S):
		(S1, S2) = (S, '')
		for i in range(len(S1) - 1, -1, -1):
			S2 += S[i]
		dp = [[0 for i in range(len(S) + 1)] for j in range(len(S) + 1)]
		a = self.solve(S1, S2, len(S1), len(S2), dp)
		return a