12960 - Palindrome

[svanegas]

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.