Palindromic Subsequence Annihilation

Moderate

0/80

0 upvote

Problem statement

You are given a string s. You can perform an operation any number of times: choose any palindromic subsequence from the string and remove it.

For each removal, you gain a score equal to the square of the length of the subsequence you removed. After a subsequence is removed, the remaining characters in the string shift to form a new, shorter string.

Your task is to find the maximum total score you can achieve by removing all characters from the string.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single string s.

Output Format:

Print a single integer representing the maximum achievable score.

Note:

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. It is not necessarily contiguous.
For example, in the string abacaba, aaaa is a palindromic subsequence.
The optimal strategy might involve removing multiple smaller palindromic subsequences rather than one large one.

Sample Input 1:

abacaba

Sample Output 1:

Explanation for Sample 1:

The entire string "abacaba" is itself a palindrome of length 7. By removing it in one operation, we get a score of 7 * 7 = 49. This is the optimal score.

Sample Input 2:

abccba

Sample Output 2:

Explanation for Sample 2:

The string "abccba" is not a palindrome. An optimal strategy is to first remove the palindromic subsequence "abcba" (length 5), which leaves the character "c".
- Score from removing "abcba": 5 * 5 = 25.
- Remaining string: "c".
- Remove the palindromic subsequence "c" (length1).Score: 1 * 1 = 1.
- Total Score: 25 + 1 = 26.

Expected Time Complexity:

The expected time complexity is O(N^3), where N is the length of the string.

Constraints:

1 <= N <= 100
`s` consists of lowercase English letters.

Time limit: 1 sec

Approaches (1)

Approach 1

Palindromic Subsequence Annihilation

Time Complexity

Time complexity is O(N^3), where N is the length of the string.

Space Complexity

(100% EXP penalty)

Palindromic Subsequence Annihilation

Console