5. Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2

Input: "cbbd"

Output: "bb"

Solutions

Solution 1

/**
 * Time complexity : O(n^3)
 * Space complexity : O(1)
 */

class Solution {
    public String longestPalindrome(String s) {
    int maxLen = 0, start = 0, n = s.length();
    for(int i = 0; i < n; i++) {
      for(int j = i+1; j <= n; j++) {
        if((j-i) > maxLen && isPalindrome(s.substring(i, j))) {
          maxLen = j-i;
          start = i;
        }
      }
        if(maxLen == n) break;
    }
    return s.substring(start, start+maxLen);
  }

  public static boolean isPalindrome(String str) {
    int n = str.length();
    for(int i = 0; i < n/2; i++) {
      if(str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;
  }
}

Solution 2

/**
 * Time complexity : O(n^2). Since expanding a palindrome around its center 
 *    could take O(n) time, the overall complexity is O(n^2).
 * Space complexity : O(1).
 */

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(s == null || n == 0) return "";
        int start = 0, end = 0;
        for(int i = 0; i < n; i++) {
            int l1 = expandAroundCenter(s, i, i);
            int l2 = expandAroundCenter(s, i, i+1);
            int len = Math.max(l1, l2);
            if((end-start) < len) {
                start = i - (len-1)/2;
                end = i + (len/2);
            }
        }
        return s.substring(start, end+1);
    }
    
    private int expandAroundCenter(String str, int left, int right) {
        while(left >= 0 && 
              right < str.length() && 
              str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return right-left-1;
    }
}

Solution 3

/**
 * Time complexity : O(n^2). This gives us a runtime complexity of O(n^2).
 * Space complexity : O(n^2). It uses O(n^2) space to store the table.
 */

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.isEmpty()) return "";
        char[] sCharArr = s.toCharArray();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        
        int start = 0, maxLen = 1;
        for(int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        for(int i = 0; i < n-1; i++) {
            if(sCharArr[i] == sCharArr[i+1]) {
                dp[i][i+1] = true;
                start = i;
                maxLen = 2;
            }
        }
        
        for(int len = 3; len <= n; len++) {
            for(int i = 0; i < n-len+1; i++) {
                int j = i+len-1;
                if(sCharArr[i] == sCharArr[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    if(len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }

        return s.substring(start, start+maxLen);
    }
}

Follow up

• Longest substring of vowels - GFG

• Longest Non-palindromic substring - GFG