Longest palindromic substring

Problem Link

5. Longest Palindromic Substring – LeetCode

Problem Statement

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

A palindromic substring is a contiguous substring that reads the same forward and backward.

Examples

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Constraints

• 1 <= s.length <= 1000

• s consists of only digits and English letters

Intuition

We are asked to find the longest contiguous palindromic substring.

The brute-force way is to try every possible substring, and for each, check if it’s a palindrome. This is time-consuming, but straightforward to implement.

Approach

1. Brute Force Strategy

   • Generate all substrings using two nested loops.

   • For each substring, check if it’s a palindrome.

   • Track the maximum-length palindrome found so far.

2. Helper Function

   • isPalindrome() checks if a string is a palindrome using two pointers.

Java Code

class Solution {
    public String longestPalindrome(String s) {
        int max = 0;
        String ans = "";
        for(int i = 0; i < s.length(); i++){
            for(int j = i; j <= s.length(); j++){
                String check = s.substring(i, j); 
                if(isPalindrome(check)){
                    max = Math.max(max, check.length());
                    if(max == check.length()){
                        ans = check;
                    }
                }
            }
        }
        return ans;
    }

    public boolean isPalindrome(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Time and Space Complexity

Dry Run

Input: "babad"

• All substrings:

  • "b" → palindrome

  • "ba" → not

  • "bab" → palindrome → update ans = "bab"

  • "baba" → not

  • "babad" → not

  • "a" → palindrome

  • "aba" → palindrome (but length same as "bab")

  • "ab" → not

  • "abad" → not

  • ...

• Final result: "bab" or "aba"

Follow-Up: Optimized Approach (Expand Around Center)

The above solution is brute force. A better approach is to expand around each center, giving time complexity O(n²) but much faster in practice:

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);     // odd length
            int len2 = expand(s, i, i + 1); // even length
            int len = Math.max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1)/2;
                end = i + len/2;
            }
        }

        return s.substring(start, end + 1);
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() &&
               s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Conclusion

This problem helps understand:

• How to identify palindromes efficiently

• String manipulation techniques

• Time trade-offs between brute force and optimized center-expansion methods

Use brute force for learning and testing, but for interviews or performance-critical code, prefer Expand Around Center.