Longest Palindromic Substring

Problem Statement

Given a string s, find and return the longest palindromic substring in s . If there are multiple answers, return any one. 

Example 1 : dabac

Answer: aba

Example 2: abc

Answer: a

Note: 'a', 'b' and 'c' are all  answers, and we can return any of the 3 answers. 

Leet Code :  https://leetcode.com/problems/longest-palindromic-substring/ 

Approaches for solving this problem 

1) Brute force approach 

From the string s, generate all possible substrings. This would need a time of O(n^2). We then need to validate if each of these substrings are palindromes or not.  Checking if a string is a palindrome would need a time of O(n). Now if we figure that the substring which we checked is a palindrome, we need to check if that is the palindrome with the maximum length we have seen so far. If so, we will update the maxPalindrome with this one. We will repeat the process for all substrings and at the end of it we will have the maxPalindrome which we can return back . Here the overall time complexity would be O(n^2) * O(n) = O(n^3)

Space complexity would be O(n) as we need to store the substring each time and also the result both of which can be of max size n. If we want to reduce the space complexity and bring it down to constant time, we can store the start and end indexes instead of storing the complete substring. This will give us O(1) space complexity 

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0 ){
        return "";
    }
    int palindromeLeft = 0, palindromeRight = 0;
    for(int i =0; i< s.length(); i++){
        for(int j=i; j < s.length(); j++){
            if(isPalindrome(s,i,j)){
                //if we found a larger palindrome,store it's start & end index
                if(j-i > palindromeRight-palindromeLeft){
                    palindromeLeft=i;
                    palindromeRight=j;
                }
            }
        }
    }
    return s.substring(palindromeLeft,palindromeRight+1);
}

public boolean isPalindrome(String s, int i, int j){
    while(i<=j){
        if(s.charAt(i)!=s.charAt(j)){
            return false;
        }
        i++;
        j--;
    }

    return true;
}

2) Dynamic Programming

From the string s, we can build substrings which are of length 1, length 2 ... length n. (where n is the length of s). Now if we take each of these category of substrings
substrings of length 1: These substrings will always be palindromes
substrings of length 2: These substrings will be palindromes if both the characters in it are the same
substrings of length 3: These will be palindromes if the first and the last character are matching. The middle character is already a palindrome (as per #1)
substrings of length 4: This will be a palindrome if the first and last character are matching and the 2 characters in the middle are already a palindrome. 
substrings of length n: This will be a palindrome if first and last character are matching and the n-2 characters in the middle are already a palindrome. 

Generalising this into a recurrence relation we can write: 

If i and j are the start and end index of the substring in s, then 

f(i,j) = true when i == j 

f(i,j) = true when j=i+1 and character at i == character at j

f(i,j) = f(i+1, j-1) is true and character at i == character at j  

We can tabulate this in a nxn 2D using Dynamic Programming. For    example, let's take an example of s = "dabac"

mapping all substrings of length 1

dp[i][i] = true

mapping all substrings of length 2

dp[i][i+1] = true, when s.charAt(i) == s.charAt(i+1)

mapping all substrings of length 3

dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1]

mapping all substrings of length 4

dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1]

mapping all substrings of length 5

dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1]

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) return "";

    boolean [][] dp = new boolean[s.length()][s.length()];

    //setting the first letter as the longest palindrome
    int leftIndexOfPalindrome = 0;
    int rightIndexOfPalindrome = 0;

    //base case : substrings with length 1
    for(int i=0;i< s.length(); i++){
        dp[i][i] = true;
        //not updating the palindrome as we already have one of length 1
    }
    //base case: substrings with length 2
    for(int i=0; i < s.length() -1 ; i++){
        int j = i+1;
        dp[i][j] = s.charAt(i) == s.charAt(j);
        //updating the palindrome if we found a lengthier one
        if( dp[i][j] && (rightIndexOfPalindrome - leftIndexOfPalindrome < j-i )){
            leftIndexOfPalindrome=i;
            rightIndexOfPalindrome=j;
        }
    }

    //substrings with length > 2
    for(int l=2; l <= s.length() ; l++){
        for(int i=0; i < s.length() -l ; i++){
            int j = i+l;
            dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
            //updating the palindrome if we found a lengthier one
            if( dp[i][j] && rightIndexOfPalindrome - leftIndexOfPalindrome < j-i ){
                leftIndexOfPalindrome=i;
                rightIndexOfPalindrome=j;
            }
        }
    }
    return s.substring(leftIndexOfPalindrome,rightIndexOfPalindrome+1);
}

The time complexity of this algorithm is O(n^2) and the space complexity is also O(n^2)

3) Expand Around the centre

If we consider any palindrome, they can be either of odd length or even length. The odd length palindromes will have a single character at the centre and an even length one will have 2 characters at the centre. Given any string s of length n, we can have 2n-1 such centres. For example, given a string abcba , the centres could be at a, b, c, b, a, ab, bc, cb, ba. Now we can expand around each of these centres and look for palindromes and capture their length. This will still have a time complexity of O(n^2), but we can optimize for space and bring down the space complexity to O(1)

public String longestPalindrome(String s) {
    int leftIndexOfPalindrome = 0;
    int rightIndexOfPalindrome = 0;
    for(int i=0; i < s.length() ; i++){
        //expanding around centre at i
        int l1 = maxPalindromeLengthAtCentre(s, i, i);
        //expanding around centre at i,i+1
        int l2 = maxPalindromeLengthAtCentre(s,i,i+1);
        int l = Math.max(l1,l2);
        //if we found a longer palindrome, store it's start & end indices
        if(l > rightIndexOfPalindrome-leftIndexOfPalindrome+1){
            //we know the centre and the length of the palindrome, 
            //finding the start & end positions of the same
            leftIndexOfPalindrome = i - (l-1)/2;
            rightIndexOfPalindrome  = i+ l/2;
        }
    }
    return s.substring(leftIndexOfPalindrome,rightIndexOfPalindrome)
}

int maxPalindromeLengthAtCentre(String s, int l, int r){
    //expanding till it's no longer a palindrome or we go out of bounds
    while(l >=0 && r < s.length() && s.charAt(l) == s.charAt(r) ){
        l--;
        r++;
    }
    //computing length, we have already crossed over, so subtracting 1
    return r-l-1;
}