Longest Palindromic Subsequence Length
Python
Hard
6 views
Problem Description
For each testcase you get string s. Output length of longest palindromic subsequence.
Input Format
First line t. Next t lines strings.
Output Format
t lines lengths.
Constraints
Total length over all testcases
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if not lines:
sys.exit(0)
try:
t=int(lines[0].strip())
except Exception:
t=0
idx=1
out=[]
for _ in range(t):
s=lines[idx] if idx<len(lines) else ''
idx+=1
n=len(s)
if n==0:
out.append('0')
continue
dp=[0]*n
for i in range(n-1,-1,-1):
prev=0
dp[i]=1
for j in range(i+1,n):
tmp=dp[j]
if s[i]==s[j]:
dp[j]=prev+2
else:
dp[j]=dp[j] if dp[j]>dp[j-1] else dp[j-1]
prev=tmp
out.append(str(dp[n-1]))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!