5. Longest Palindromic Substring

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

Example:

Input:
 "babad"


Output:
 "bab"


Note:
 "aba" is also a valid answer.

Example:

Input:
 "cbbd"


Output:
 "bb"

Solution

(1) Java

Expand around the center, it is O(n^2)

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int[] range = new int[2];
        for (int i = 0; i < s.length(); i++) {
            findPalindrome(s, i, i, range);
            findPalindrome(s, i, i+1, range);
        }
        return s.substring(range[0], range[1]+1);
    }

    private void findPalindrome(String s, int i, int j, int[] range) {
        while (i >= 0 && j < s.length()) {
           if (s.charAt(i) == s.charAt(j)) {
               if (j-i > range[1]-range[0]) {
                   range[0] = i;
                   range[1] = j;
               }
               i--;
               j++;
           } else {
               return;
           }
        }        
    }
}

(2) Python

DP passed

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return s
        length = len(s)
        dp = [[False for j in range(length)] for i in range(length)]
        (start,end) = (0,0)
        for l in range(1, length+1):
            for i in range(length-l+1):
                j = i+l-1
                if s[i] == s[j] and (j-i<=2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if j-i>end-start:
                        (start,end) = (i,j)
        return s[start:end+1]

(3) Scala

Although ugly, still works

object Solution {
    def longestPalindrome(s: String): String = {
        val input: Option[String] = Some(s)
        input match {
            case None => null
            case _ => helper(s, 0)
        }
    }

    def helper(s: String, idx: Int): String = {
        if (idx == s.length()) {
            return ""
        }
        val s1 = getPalindrome(s, idx, idx)
        val s2 = getPalindrome(s, idx, idx+1)
        val s3 = s1.length()-s2.length() match {
            case x if x >= 0 => s1
            case y if y < 0 => s2
        }
        val s4 = helper(s, idx+1)
        val s5 = s3.length()-s4.length() match {
            case x if x >= 0 => s3
            case y if y < 0 => s4
        }
        return s5
    }

    def getPalindrome(s: String, idx: Int, nextIdx: Int): String = {
        var left = idx
        var right = nextIdx
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                left -= 1
                right += 1
            } else {
                return s.substring(left+1, right)
            }
        }
        return s.substring(left+1, right)
    }
}