5. Longest Palindromic Substring LeetCode Solution

In this guide we will provide 5. Longest Palindromic Substring LeetCode Solution with best time and space complexity. The solution to Longest Palindromic Substring problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Table of Contents

5. Longest Palindromic Substring LeetCode Solution image

Problem Statement of Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Complexity Analysis

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

5. Longest Palindromic Substring LeetCode Solution in C++

class Solution {
 public:
  string longestPalindrome(string s) {
    if (s.empty())
      return "";

    // (start, end) indices of the longest palindrome in s
    pair<int, int> indices{0, 0};

    for (int i = 0; i < s.length(); ++i) {
      const auto [l1, r1] = extend(s, i, i);
      if (r1 - l1 > indices.second - indices.first)
        indices = {l1, r1};
      if (i + 1 < s.length() && s[i] == s[i + 1]) {
        const auto [l2, r2] = extend(s, i, i + 1);
        if (r2 - l2 > indices.second - indices.first)
          indices = {l2, r2};
      }
    }

    return s.substr(indices.first, indices.second - indices.first + 1);
  }

 private:
  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  pair<int, int> extend(const string& s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s[i] != s[j])
        break;
    return {i + 1, j - 1};
  }
};
/* code provided by PROGIEZ */

5. Longest Palindromic Substring LeetCode Solution in Java

class Solution {
  public String longestPalindrome(String s) {
    if (s.isEmpty())
      return "";

    // (start, end) indices of the longest palindrome in s
    int[] indices = {0, 0};

    for (int i = 0; i < s.length(); ++i) {
      int[] indices1 = extend(s, i, i);
      if (indices1[1] - indices1[0] > indices[1] - indices[0])
        indices = indices1;
      if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
        int[] indices2 = extend(s, i, i + 1);
        if (indices2[1] - indices2[0] > indices[1] - indices[0])
          indices = indices2;
      }
    }

    return s.substring(indices[0], indices[1] + 1);
  }

  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  private int[] extend(final String s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s.charAt(i) != s.charAt(j))
        break;
    return new int[] {i + 1, j - 1};
  }
}
// code provided by PROGIEZ

5. Longest Palindromic Substring LeetCode Solution in Python

class Solution:
  def longestPalindrome(self, s: str) -> str:
    if not s:
      return ''

    # (start, end) indices of the longest palindrome in s
    indices = [0, 0]

    def extend(s: str, i: int, j: int) -> tuple[int, int]:
      """
      Returns the (start, end) indices of the longest palindrome extended from
      the substring s[i..j].
      """
      while i >= 0 and j < len(s):
        if s[i] != s[j]:
          break
        i -= 1
        j += 1
      return i + 1, j - 1

    for i in range(len(s)):
      l1, r1 = extend(s, i, i)
      if r1 - l1 > indices[1] - indices[0]:
        indices = l1, r1
      if i + 1 < len(s) and s[i] == s[i + 1]:
        l2, r2 = extend(s, i, i + 1)
        if r2 - l2 > indices[1] - indices[0]:
          indices = l2, r2

    return s[indices[0]:indices[1] + 1]
#code by PROGIEZ

Additional Resources

See also  3. Longest Substring Without Repeating Characters LeetCode Solution

Feel free to give suggestions! Contact Us