Palindrome

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward, such as madam or kayak.

To check if a given string is palindrome or not, take two pointers approach, first pointer at the start and 2nd pointer at the end, start comparing characters at those index while incrementing the first index and decrementing the 2nd till a mismatch is found or the pointers meet each other at the centre. If NO mismatch is found, the string is a palindrome else it is not. Complexity of this algorithm is linear O(n).

public static boolean isPalindrome(final String str) {
    int start = 0;
    int end = str.length() - 1;
    while (start < end) {
        if (str.charAt(start) != str.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

palindrome

Now, if we modify the same problem statement to check if a given string or any of its substring is a palindrome.
The hasPalidrome() method will return length of substring which is a palindrome, in worst-case it will return 1 (remember, every character is a palindrome).

public static int hasPalindrome(final String str) {
    for (int i = 0; i < str.length() - 1; i++) {                                  for (int j = str.length() - 1; j > i; j--) {
            if (isPalindrome(str, i, j)) {
                return j - i + 1;
            }
        }
    }
    return 1;
}

Over here, we are using the isPalindrome subroutine to check if a given string from index start to end is a palindrome or not.

substring-palindrome.png

If we update the above problem statement again to return the length of longest substring which is a palindrome, the above algorithm will NOT work since it will return length of the first palindrome that is found and not necessarily the longest.

For ex: If we modify our original string madam and prefix it with ‘a’, it becomes amadam.

The above algorithm will return length 3 for ‘amadam’ which is a valid palindrome however not the longest, which is still ‘amadam‘ of length 5.

The reason above algorithm does not work for longest palindrome is because we terminate the moment we find the first palindrome. We can modify the above to maintain a max length variable and keep updating it as and when we find a new palindrome of longer length, this is nothing but a brute force approach where we are evaluating all substrings.

A slightly better approach is to first evaluate longer substrings, since the moment we find a substring which is a palindrome, its length will always be greater than any palindrome that can be found within that substring itself and hence we do not have to evaluate any substrings within that substring further.

A naive recursive approach is to find if the given string is a palindrome, if not, find maximum length palindrome in left and right substring.

public static int maxPalindromeLength(final String str, int start, int end){
    //Condition to break recursion
    if (start >= end) {
        return 1;
    }

    if (isPalindrome(str, start, end)) {
        return end - start + 1; 
    }

    //return longest substring of left and right substring.
    return Math.max(
        //longest palindrome in left substring.
        maxPalindromeLength(str, start, end - 1),
        //longest palindrome in right substring.  
        maxPalindromeLength(str, start + 1, end)
    );
}

recursive-palindrome.png

The complexity of this algorithm is exponential O(2^n), since with every increase in n, the total number of comparisons increases exponentially.

The below recursion tree shows total number of comparisons done for n=2, 3 and 4.

recursionTree-palindrome.png

Over here we are comparing the same substring “bc” twice, hence this problem has overlapping subproblems property of dynamic programming approach.

A bottom up approach is to first evaluate smaller substrings and use those results during further evaluation. In other words, a string is a palindrome provided the first and last character matches and substring between those characters is also a palindrome. Hence a string S(0,n) is a palindrome provided character at 0 and n matches and S(0+1, n-1) is also a palindrome. So we can use result of S(0+1, n-1) while evaluating S(0, n), hence this problem has optimal substructure property of dynamic programming approach as well.

Re-computation of overlapping subproblems can be avoided by using a lookup table L[][].

L[i][j] is a palindrome if character at i and j matches and L[i+1][j-1] is also a palindrome.

if (character at i and j matches && L[i+1][j-1] is a palindrome) {
    L[i][j] = L[i+1][j-1] + 2; // length of inner palindrome + 2
}
else {
    L[i][j] = -1; // not a palindrome
}

We start analyzing all substrings of length 2 and use those results while analyzing all substrings of length 3, and so on and so forth.

public static int longestPalindrome(final String str) {
    int length = str.length();
    int [][] L = new int[length][length];

    for (int i = 0; i < length; i ++) {
        for (int j = 0; j < length; j++) {
            //Every character is a palindrome of length 1.
            L[i][j] = (i == j) ? 1 : -1;
        }
    }

    int subStrLength = 2;
    while (subStrLength <= length) {
        for (int i = 0; i < length - subStrLength + 1; i++) {
            int j = i + subStrLength - 1; //end index of substring.
            if ((subStrLength == 2 || L[i+1][j-1] != -1) && 
                str.charAt(i) == str.charAt(j)) {
                L[i][j] = L[i+1][j-1] + 2;
            }
            else {
                L[i][j] = -1;
            }
        }
        subStrLength++;
    }
    return max(L);
}

The complexity of above algorithm is O(n^2).

Git:
algorithms/src/main/java/org/nmn/notes/algorithms/dp/Palindrome.java

References:
https://en.wikipedia.org/wiki/Palindrome

Advertisements