Longest Palindromic Subsequence Length

Longest Palindromic Subsequence Length

Hard Python Loops 17 views
Explanation Complexity

Problem Statement

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.

Example

2
bbbab
cbbd
4
2

Constraints

Total length over all testcases

Input / Output Format

Input Format
First line t. Next t lines strings.
Output Format
t lines lengths.
Constraints
Total length over all testcases

Examples

Input:
2 bbbab cbbd
Output:
4 2

Example Solution (Public)

Python 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.