CareerCup

it equals with finding the longest common subsequence between one word (e.g. XAYBZBA) and its reverse (e.g. ABZBYAX).

This problem can be solved by using dynamic programming
Let LP(i,j)= length of longest palindromic subsequence in array X from index i to j
LP(i,j) = LP(i+1,j-1) + 2 if X[i] = X[j]
= max [ LP(i+1,j), LP(i,j-1) ] if X[i]!=X[j]
= 1 if i=j
= 1 if i=j-1 and X[i]!=X[j]
=2 if i=j-1 and X[i] = X[j]

To understand this solution you can watch this wonderful video lecture

youtube.com/watch?v=Mbav2iuJ7xQ

this algo will only return length......can anyone post running code along with length and longest palindrome string?

public int LongestPalindrome(char[] str, int i, int j)
        {
            if (str == null) 
            {
                throw new ArgumentNullException("str");
            }

            if (str.Length == 0) 
            {
                return 0;
            }

            if (str[i] == str[j] && i == j - 1) 
            {
                return 2;
            }

            if (str[i] == str[j] && i == j) 
            {
                return 1;
            }

            if (str[i] == str[j])
            {
                return this.LongestPalindrome(str, i + 1, j - 1) + 2;
            }

            return Math.Max(this.LongestPalindrome(str, i + 1, j), this.LongestPalindrome(str, i, j - 1));
 }

yeah it is easy in java...........i need c/c++ code

ur code only return max length but i need to return max palindrome string

Let A be the input string and B is its reverse, then following DP algo can be used to solve this problem

public static void evaluate(String A, String B) {

		int x = A.length() + 1;
		int y = B.length() + 1;
		int[][] M = new int[x][y];

		for (int i = 1; i < x; i++) {
			for (int j = 1; j < y; j++) {
				if (A.charAt(i - 1) == B.charAt(j - 1))
					M[i][j] = M[i - 1][j - 1] + 1;
				else
					M[i][j] = Math.max(M[i - 1][j], M[i][j - 1]);
			}
		}
		
		Stack<Character> stack = new Stack<Character>();
		
		int startX = x - 1;
		int startY = y - 1;
		
		while(startX >= 1 && startY >= 1) {
			if(A.charAt(startX - 1) == B.charAt(startY - 1)) {
				stack.add(A.charAt(startX - 1));
				
				startX--;
				startY--;
			} else {
				if(M[startX - 1][startY] >= M[startX][startY - 1]) 
					startX--;
				else
					startY--;
			}
		}
		
		while (!stack.isEmpty()) 
			System.out.print(stack.pop());
	}

geeksforgeeks(dot)org/dynamic-programming-set-12-longest-palindromic-subsequence/

static String LPS(int i, int j, String s) {
        if (i > j) return "";
        if (i == j) return s.charAt(i) + "";
        if (s.charAt(i) == s.charAt(j))
            return s.charAt(i) + LPS(i + 1, j - 1, s) + s.charAt(j);
        String a = LPS(i + 1, j, s);
        String b = LPS(i, j - 1, s);
        return (a.length() > b.length()) ? a : b;
    }