Longest Hidden Palindrome

Medium

You are given a string text. Cross out any characters (possibly none) so that the remaining characters, in their original order, form a palindrome: a string that reads the same left to right and right to left. Return the greatest length of a palindrome you can get this way.

Example 1

text="racecars" → 7

Crossing out the final "s" leaves "racecar", a palindrome of length 7.

Example 2

text="qxwxe" → 3

For example "xwx", length 3.

Example 3

text="abcd" → 1

All letters differ, so only a single letter is a palindrome.

Constraints

1 ≤ len(text) ≤ 1000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium

Input

text="racecars"

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.