You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern: X1,X2,X3…Xn,Xn,…X3,X2,X1 where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1<=i< n.
Input: The string: S
Output: The integer: 2n
Sample input 1: “acdbdea”
Sample output 1: 4
Explanation: “adda” is the longest subsequence following the given pattern.
Sample input 2: “abbacdeedc”
Sample output 2: 6
Explanation: “cdeedc” is the longest subsequence following the given pattern.
Sample input 3: “taker”
Sample output 3: 0
Explanation: No subsequence follows the given pattern.
This question was asked in a coding interview and I didn’t know how to solve it. I understood how to find longest palindromic sub sequence but don’t know how to implement the unique adjacent character part. Please help. pseudo code is fine