Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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
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));
}
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());
}
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;
}
it equals with finding the longest common subsequence between one word (e.g. XAYBZBA) and its reverse (e.g. ABZBYAX).
- wangbingold July 31, 2012