Two Disjoint Palindromic Picks

Medium

You get a string text of lowercase English letters. Choose two subsequences of it so that each reads the same forwards and backwards and no position of the string is used by both. Return the largest possible product of their lengths. A subsequence is what remains after deleting some characters (possibly none) without changing the order of the rest.

Example 1

text="racecars" → 12

Take "raar" (positions 0, 1, 5, 6) and "cec" (positions 2, 3, 4): no shared positions, both are palindromes, 4 · 3 = 12. Taking all of "racecar" leaves only "s" for the other, giving just 7 · 1 = 7.

Example 2

text="xy" → 1

Every single letter is a palindrome: "x" and "y", 1 · 1 = 1.

Constraints

2 ≤ len(text) ≤ 12
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation String Dynamic Programming Backtracking Bitmask

Similar problems

Best Word Set From Tiles Hard Nine-Dot Lock Patterns Medium Square Frame From Sticks Medium Seating by Divisibility Medium Cheapest Basket with Bundles Medium

Input

text="racecars"

Expected

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