algoadvance

Leetcode 5. Longest Palindromic Substring

Problem Statement

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

Clarifying Questions

  1. What is a palindrome?
    A palindrome is a string that reads the same forward and backward.

  2. Input Constraints:
    • Is the input string s non-empty?
      Yes, assume the input string is non-empty.
    • What is the maximum length of the string?
      The length of the string can be up to 1000 characters.
  3. Output Constraints:
    • If there are multiple substrings with the same maximum length, can we return any of them?
      Yes, returning any one of them is acceptable.

Strategy

Expanding Around Center

  1. Basic Idea:
    • A palindromic string mirrors around its center.
    • We can expand around each character and each pair of consecutive characters to find all palindromes.
  2. Algorithm Steps:
    • Initialize variables to keep track of the start and maximum length of the longest palindrome found.
    • Loop through each character in the string and consider it as the center of a palindrome.
    • Expand around the center for both:
      • Odd length palindromes (single character center).
      • Even length palindromes (pair of characters as center).
    • For each expanded palindrome, check its length and update the start and maximum length variables if it’s the longest palindrome found so far.
    • Finally, return the substring starting from the recorded start position with the recorded maximum length.

Time Complexity

Code

#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        int start = 0, maxLength = 1;
        
        for (int i = 0; i < s.length(); ++i) {
            // Odd length palindromes
            expandAroundCenter(s, i, i, start, maxLength);
            // Even length palindromes
            expandAroundCenter(s, i, i + 1, start, maxLength);
        }
        
        return s.substr(start, maxLength);
    }
    
private:
    void expandAroundCenter(const string& s, int L, int R, int& start, int& maxLength) {
        while (L >= 0 && R < s.length() && s[L] == s[R]) {
            --L;
            ++R;
        }
        
        int len = R - L - 1; // Length of the currently found palindrome
        if (len > maxLength) {
            start = L + 1;
            maxLength = len;
        }
    }
};

This code defines a class Solution that contains a method longestPalindrome to find the longest palindromic substring. The helper method expandAroundCenter is used to expand around potential centers and update the longest palindrome found during the process.

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