Problem of The Day: Longest Palindromic Substring

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def getLargestPalindrome(self, l, r, s):
        if l < 0:
            return (0, 0)
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return (l + 1, r - 1)

    def longestPalindrome(self, s: str) -> str:
        res = ""

        for i, c in enumerate(s):
            odd_left, odd_right = self.getLargestPalindrome(i, i, s)
            even_left, even_right = self.getLargestPalindrome(i - 1, i, s)
            odd_length = odd_right - odd_left + 1
            even_length = even_right - even_left + 1
            if odd_length > even_length:
                if len(res) < odd_length:
                    res = s[odd_left:odd_right + 1]
            else:
                if len(res) < even_length:
                    res = s[even_left:even_right + 1]

        return res

public class Solution {
    public string GetPalindrome(int l, int r, string s) {
        if (l < 0)
            return "";
        while (l >= 0 && r < s.Length && s[l] == s[r]) {
            l -= 1;
            r += 1;
        }
        int left = l + 1;
        int right = r - 1;
        return s.Substring(left, right - left + 1);
    }

    public string LongestPalindrome(string s) {
        string res = "";
        for (int i = 0; i < s.Length; i++) {
            string odd = GetPalindrome(i, i, s);
            string even = GetPalindrome(i - 1, i, s);
            if (odd.Length > even.Length) {
                if (res.Length < odd.Length) {
                    res = odd;
                }
            }
            else {
                if (res.Length < even.Length) {
                    res = even;
                }
            }
        }

        return res;
    }
}

• Time: O(n^2)
• Space: O(1)

Editorial

Approach 1: Check All Substrings

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(i, j):
            left = i
            right = j - 1

            while left < right:
                if s[left] != s[right]:
                    return False

                left += 1
                right -= 1

            return True

        for length in range(len(s), 0, -1):
            for start in range(len(s) - length + 1):
                if check(start, start + length):
                    return s[start : start + length]

        return ""

public class Solution {
    public string LongestPalindrome(string s) {
        for (int length = s.Length; length > 0; length--) {
            for (int start = 0; start <= s.Length - length; start++) {
                if (Check(start, start + length, s)) {
                    return s.Substring(start, length);
                }
            }
        }

        return "";
    }

    private bool Check(int i, int j, string s) {
        int left = i;
        int right = j - 1;

        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

Approach 2: Dynamic Programming

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = [0, 0]

        for i in range(n):
            dp[i][i] = True

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                ans = [i, i + 1]

        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    ans = [i, j]

        i, j = ans
        return s[i : j + 1]