Scale Engineer

Longest Palindromic Substring

Med
#0005Time: O(n^3)Space: O(1)73 companies
Patterns
Two PointersDynamic Programming
Data structures
String
Companies
AccentureAccoliteAdobeAgoda

Prompt

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.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach is the most straightforward but also the most inefficient. The core idea is to check every single substring of the input string s and determine if it's a palindrome. We maintain a variable to keep track of the longest palindromic substring found so far.

Algorithm

  • Initialize maxLength = 1 and start = 0.
  • Iterate through the string with a starting index i from 0 to n-1.
  • For each i, iterate with an ending index j from i to n-1.
  • Extract the substring sub from i to j.
  • Check if sub is a palindrome. This check takes O(length of sub) time.
  • If sub is a palindrome and its length is greater than maxLength, update maxLength and start.
  • After all substrings are checked, return the substring starting at start with length maxLength.

Walkthrough

This approach is the most straightforward but also the most inefficient. The core idea is to check every single substring of the input string s and determine if it's a palindrome. We maintain a variable to keep track of the longest palindromic substring found so far.

Algorithm

  1. Initialize variables maxLength to 1 and start to 0 to store the length and starting index of the longest palindrome.
  2. Use nested loops to generate all possible substrings. The outer loop (with index i) selects the starting character, and the inner loop (with index j) selects the ending character.
  3. For each substring s[i...j], call a helper function isPalindrome to check if it's a palindrome.
  4. The isPalindrome check is done by comparing characters from both ends of the substring, moving inwards. This takes time proportional to the length of the substring.
  5. If the current substring is a palindrome and its length is greater than maxLength, update maxLength and start.
  6. After checking all substrings, the longest palindromic substring is s.substring(start, start + maxLength).

Code

class Solution {    public String longestPalindrome(String s) {        if (s == null || s.length() < 1) return "";        int n = s.length();        int start = 0;        int maxLength = 1;         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                int len = j - i + 1;                if (len > maxLength && isPalindrome(s, i, j)) {                    maxLength = len;                    start = i;                }            }        }        return s.substring(start, start + maxLength);    }     private boolean isPalindrome(String s, int low, int high) {        while (low < high) {            if (s.charAt(low++) != s.charAt(high--)) {                return false;            }        }        return true;    }}

Complexity

Time

O(n^3)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space (O(1) auxiliary space).

Cons

  • Extremely inefficient with a time complexity of O(n^3).

  • Will likely result in a 'Time Limit Exceeded' error for larger inputs (e.g., n=1000).

Solutions

public class Solution {    public string LongestPalindrome(string s) {        int n = s.Length;        bool[, ] f = new bool[n, n];        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; ++j) {                f[i, j] = true;            }        }        int k = 0, mx = 1;        for (int i = n - 2; i >= 0; --i) {            for (int j = i + 1; j < n; ++j) {                f[i, j] = false;                if (s[i] == s[j]) {                    f[i, j] = f[i + 1, j - 1];                    if (f[i, j] && mx < j - i + 1) {                        mx = j - i + 1;                        k = i;                    }                }            }        }        return s.Substring(k, mx);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem