algoadvance

Leetcode 5. Longest Palindromic Substring

Problem Statement

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

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the string s?
    • Are there any constraints on the type of characters in s (e.g., only lowercase English letters)?
  2. Output Requirements:
    • If there are multiple substrings with the same maximum length, is any one of them acceptable to return?
  3. Edge Cases:
    • What should be returned if the string is empty?
    • What should be returned if the string has only one character?

Strategy

To solve the problem efficiently, we can use the “Expand Around Center” approach. The idea is to consider every possible center of the palindrome (considering both odd-length and even-length centers) and expand outwards to find the longest palindromic substring for each center.

  1. Initialize:
    • Initialize a variable to keep track of the start and end indices of the longest palindrome found.
  2. Expand Around Center:
    • For each character in the string, consider it as the center of an odd-length palindrome.
    • For each pair of consecutive characters, consider them as the center of an even-length palindrome.
    • For each center, expand outwards as long as the substring remains a palindrome.
  3. Update the Longest Palindrome:
    • Keep track of the maximum length palindrome found so far and update the start and end indices accordingly.
  4. Return the Result:
    • Finally, return the substring using the start and end indices.

This approach ensures we check all potential palindromic centers and efficiently find the longest one.

Code

public 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 = expandAroundCenter(s, i, i); // Odd-length palindromes
            int len2 = expandAroundCenter(s, i, i + 1); // Even-length palindromes
            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 expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Time Complexity

The time complexity of this approach is O(n^2), where n is the length of the input string. This is because for each character, we expand around the center for potentially all characters (both for odd-length and even-length palindromes).

Space Complexity

The space complexity is O(1). No extra space proportional to the input size is used; only a few variables for indexing and calculation are utilized.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI