// Palindromic Subsequence - DP

// Longest palindromic subsequence of a string
using namespace std;

#include <iostream>
#include <string>
#include <vector>

class LPS {

public:
  int findLPSLength(const string &st) {
    vector<vector<int>> dp(st.length(), vector<int>(st.length(), 0));
    // every sequence with one element is a palindrome of length 1
    for (int i = 0; i < st.length(); i++) {
      dp[i][i] = 1;
    }

    for (int l = 1; l < st.size(); l++) { // take length of string as a factor and findout best
    // palindromic substring with that length
      for (int j = l; j < st.size(); j++) {
        // 2 + best palindromic string in between them
        if (st[j-l] == st[j]) {
          dp[j-l][j] = 2 + dp[j-l+1][j-1];
        } else {
          // take maximum either including this character or excluding this character
          // inorder to maintain string length, check different matrices.
          dp[j-l][j] = max(dp[j-l+1][j], dp[j-l][j-1]);
        }
      }
    }
    return dp[0][st.size() - 1];
  }
};

int main(int argc, char *argv[]) {
  LPS *lps = new LPS();
  cout << lps->findLPSLength("abdbca") << endl;
  cout << lps->findLPSLength("cddpd") << endl;
  cout << lps->findLPSLength("pqr") << endl;

  delete lps;
}

// Longest palindromic substring length
class LPS {

public:
  int findLPSLength(const string &st) {
    // dp[i][j] will be 'true' if the string from index 'i' to index 'j' is a palindrome
    vector<vector<bool>> dp(st.length(), vector<bool>(st.length()));

    // every string with one character is a palindrome
    for (int i = 0; i < st.length(); i++) {
      dp[i][i] = true;
    }

    int maxLength = 1;
    for (int l = 1; l < st.length(); l++) {
      for (int j = l; j < st.length(); j++) {
        if (st[j-l] == st[j]) {
          // if it's a two character string or if the remaining string is a palindrome too
          if (dp[j - l + 1][j - 1]) {
            dp[j-l][j] = true;
            maxLength = max(maxLength, l + 1);
          }
        }
      }
    }

    return maxLength;
  }
};

// Count of palindromic substrings
class CPS {
public:
  int findCPS(const string &st) {
    // dp[i][j] will be 'true' if the string from index 'i' to index 'j' is a palindrome
    vector<vector<bool>> dp(st.length(), vector<bool>(st.length()));
    int count = 0;

    // every string with one character is a palindrome
    for (int i = 0; i < st.length(); i++) {
      dp[i][i] = true;
      count++;
    }

    for (int l = 1; l < st.size(); l++) {
      for (int j = l; j < st.length(); j++) {
        if (st[j-l] == st[j]) {
          // if it's a two character string or if the remaining string is a palindrome too
          if (dp[j-l + 1][j - 1]) {
            dp[j-l][j] = true;
            count++;
          }
        }
      }
    }

    return count;
  }
};

// Minimum deletions/additions to make a string palindrome

Minimum_deletions_to_make_palindrome = Length(st) - LongestPalindromicSubsequence(st)