« Longest Palindrome subsequence

Given a sequence, find the length of the longest palindromic subsequence in it.

Input:

GeeksForGeeks

Output:

5

This contains many palindrome subsequences like EEKEE, EESEE, EEFEE

Efficient alogorithm with O(n2) DP algorithm

Copy
1#include<iostream>
2#include<iomanip>
3#include<algorithm>
4#include<string>
5#include<cstring>
6#include<vector>
7#include<cmath>
8#include <map>
9#include<climits>
10//climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int longestPalindromeSubstring(string str){
15    int n = str.length();
16    vector<vector<int> > vec(n, vector<int>(n, 0));
17
18    for (int i = 0; i < n; i++){
19        vec[i][i] = true;
20    }
21
22    for(int k =2; k<=n;k++){
23        for(int i=0; i<n-k+1; i++){
24            int j = i + k -1;
25            if(str[i] == str[j] && k == 2){
26                vec[i][j] = 2;
27            }else if(str[i] == str[j]){
28                vec[i][j] = 2 + vec[i+1][j-1];
29            }else{
30                vec[i][j] = max(vec[i][j-1], vec[i+1][j]);
31            }
32        }
33    }
34
35    return vec[0][n-1];
36}
37int main()
38{
39    string str;
40    cin >> str;
41    cout << "Length is: "<< longestPalindromeSubstring(str)<<endl;
42    return 0;
43}

Inefficient algorithm using recursion

Copy
1#include<iostream>
2#include<iomanip>
3#include<algorithm>
4#include<string>
5#include<cstring>
6#include<vector>
7#include<cmath>
8#include <map>
9#include<climits>
10//climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int longestPalindromeSubstring(string str, int i, int j){
15    if(i == j){
16        return 1;
17    }
18
19    if (str[i] == str[j] && i + 1 == j){
20        return 2;
21    }
22
23    if(str[i] == str[j]){
24        return longestPalindromeSubstring(str, i+1, j-1) + 2;
25    }
26
27    return max( longestPalindromeSubstring(str, i, j-1), longestPalindromeSubstring(str, i+1, j) );
28}
29
30
31int main()
32{
33    string str;
34    cin >> str;
35    cout << "Length is: "<< longestPalindromeSubstring(str, 0, str.length()-1)<<endl;
36    return 0;
37}