All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

D.Special Palindrome
Tag(s):
No tags
Problem
Editorial
Analytics

Given a String S and a character C, find the length of the longest palindromic subsequence of S containing the character C.

Input

  • The First Line contains an integer denoting the number of testcases.
  • Each testcase is of 2 lines. 
    • The First line contains one character C 
    • The Second line contains the string S 

Output 

For every testcase print the maximum length on a new line.

Constraints

  • 1 <= T <= 10
  • 1 <= |S| <= 1000
  • Both and are made up of small English alphabets.
SAMPLE INPUT
2
a
dcbabcd
b
bbbb
SAMPLE OUTPUT
7
4
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?