Given an array A of lower case characters $$$a_1,a_2,....,a_n$$$ we need to perform the following operation until it becomes empty,
Select a segment $$$(l,r)$$$ such that $$$a_l=a_{l+1}=a_{l+2}=....=a_r$$$ and remove the segment from the array.
Add the square of length of segment to your score and rearrange the remaining elements.
Output the maximum score that can be obtained.(score is initialized to 0).
Constraints: n <= 100 (If I recall correctly)
input
2
6
a a b b a c
12
a b a b a b a b a b a b
output
14
42
Hi bro
My Hint
Dynamic programming?
Hint2
sub-segments
It can be solved using Dynamic Programming by maintaining 2 states(l,r)
If there's only one element (l == r), then dp[l][r] = 1
If the segment A[l:r+1] consists of identical characters (A[l] == A[r] for all l <= i <= r), remove it as a whole to get dp[l][r] = (r-l+1)^2
For any two indices k where l <= k < r, split the segment A[l:r+1] into A[l:k] and A[k+1:r], and maximize the score by combining scores from these subarrays.
The complexity using this can go till O(n^3) which works for N <= 100