## 12960 - Palindrome

Moderator: Board moderators

svanegas
New poster
Posts: 1
Joined: Sun Oct 04, 2015 6:55 pm

### Re: 12960 - Palindrome

Hello,

I'm trying to solve this problem using the same concept of Longest Palindromic Subsequence. I'm not working with a single-value state but I'm using 2-values state, because we have to maximize the number of special characters and the palindrome length.

I'm using a struct to represent each state, as follows.

Code: Select all

``````struct state {
int len, spec;
state() {}
state(int _len, int _spec) : len(_len), spec(_spec) {}
bool operator < (const state &than) const {
if (spec < than.spec) return true;
else if (spec == than.spec) return len < than.len;
else return false;
}
};
``````
- len: Represents the current state palindrome length.
- spec: Represents how many special characters I am including in the current state palindrome.

Notice how the bool operator < function maximizes first by number of special characters and then by length.

Our function looks like this:

Code: Select all

``````state
lps(const string &seq, int i, int j) { ... }
``````
Now, we have four cases in each state for solving the Longest Palindromic Subsequence recursion:

Base case 1: If there is only one character, that character is a palindrome itself, and if it is a special character our spec attribute should be 1, or 0 otherwise.

Code: Select all

``````if (i == j) return state(1, is_spec[i]);
``````
* is_spec is a boolean array, where is true if the character i is special, false otherwise

Base case 2: If there are only 2 characters and both are the same, the length of the palindrome is 2 and we add each special character.

Code: Select all

``````if (seq[i] == seq[j] && i + 1 == j) return state(2, is_spec[i] + is_spec[j]);
``````
Case 3: If the first and last characters match, we take the center sequence (not including i neither j) and add 2 to the length, and we add special characters if needed.

Code: Select all

``````if (seq[i] == seq[j]) {
state ret = lps(seq, i + 1, j - 1);
ret.len += 2;
ret.spec += (is_spec[i] + is_spec[j]);
return ret;
}
``````
Case 4: If the first and last characters don't match, we take the maximum between center state including i and center state including j.

Code: Select all

``````if (seq[i] != seq[j]) return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
``````
The answer for the problem would be:

Code: Select all

``````lps(seq, 0, seq.size() - 1).len
``````
However, I don't understand why I'm getting Wrong Answer. Could anyone explain me what I'm doing wrong? Or maybe a case that fails with this solution?

Thanks a lot.