Even Palindrome Without Twins

Medium

Call a string a *tidy palindrome* if: - it reads the same forwards and backwards; - its length is even; - no two adjacent letters in it are equal, except for the two in the middle. For example, xyyx and abccba are tidy palindromes, while xyx (odd length) and xxxx (equal neighbors away from the middle) are not. You are given a string text. Pick a subsequence of it (some of its letters in their original order, not necessarily adjacent) that is a tidy palindrome, and return the greatest possible length. If there is none, return 0.

Example 1

text="cabbac" → 6

The whole string is an even-length palindrome, and the only equal neighbors are the middle pair bb.

Example 2

text="aaaa" → 2

aaaa does not count, since equal letters sit next to each other outside the middle. The best is aa, of length 2.

Example 3

text="xyz" → 0

No letter repeats, so there is no suitable palindrome at all.

Constraints

1 ≤ len(text) ≤ 250
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="cabbac"

Expected

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