### Re: 12960 - Palindrome

Posted:

**Sun Oct 04, 2015 7:43 pm**Hello,

I'm trying to solve this problem using the same concept of

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

Notice how the

Our function looks like this:
Now, we have four cases in each state for solving the

The answer for the problem would be:
However, I don't understand why I'm getting

Thanks a lot.

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) { ... }
```

*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));
```

Code: Select all

```
lps(seq, 0, seq.size() - 1).len
```

**. Could anyone explain me what I'm doing wrong? Or maybe a case that fails with this solution?***Wrong Answer*Thanks a lot.