Longest Palindromic Substring DSA Solution - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 2: Strings

Learning Outcome

After this lesson, you should be able to use the symmetry of palindromes and expand from centers instead of generating every substring.

Problem Statement

Given a string s, return the longest palindromic substring in s. The substring must be contiguous.

Brute Force Approach

Generate every substring and check whether it is a palindrome. Keep the longest valid one.

This is very direct, but checking many substrings and validating each one can reach O(n^3).

Optimized Approach

Every palindrome has a center. For each index, expand once for odd-length palindromes and once for even-length palindromes. Track the best range found.

Exact Pseudocode

bestStart = 0
bestLength = 1
expand(left, right):
  while left >= 0 and right < length(s) and s[left] == s[right]:
    update best range if right - left + 1 is larger
    left = left - 1
    right = right + 1
for center from 0 to length(s) - 1:
  expand(center, center)
  expand(center, center + 1)
return substring(bestStart, bestLength)

Reference Code

class Solution:
    def longestPalindrome(self, s):
        if not s:
            return ""

        best_start = 0
        best_len = 1

        def expand(left, right):
            nonlocal best_start, best_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                length = right - left + 1
                if length > best_len:
                    best_start = left
                    best_len = length
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)
            expand(center, center + 1)

        return s[best_start:best_start + best_len]

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

        int bestStart = 0;
        int bestLen = 1;

        auto expand = [&](int left, int right) {
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                int len = right - left + 1;
                if (len > bestLen) {
                    bestStart = left;
                    bestLen = len;
                }
                left--;
                right++;
            }
        };

        for (int center = 0; center < s.size(); center++) {
            expand(center, center);
            expand(center, center + 1);
        }

        return s.substr(bestStart, bestLen);
    }
};

class Solution {
    private int bestStart = 0;
    private int bestLen = 1;

    public String longestPalindrome(String s) {
        if (s.length() == 0) return "";

        for (int center = 0; center < s.length(); center++) {
            expand(s, center, center);
            expand(s, center, center + 1);
        }

        return s.substring(bestStart, bestStart + bestLen);
    }

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

Sample Dry Run

Complexity

Edge Cases

• Empty string if platform allows it.
• Single-character string.
• Even-length palindrome such as "bb".

Interview Checklist

• Handle both odd and even centers.
• Track indices, not only the substring.
• Return any valid longest palindrome if multiple exist.

FAQs

Because palindromes are symmetric, so a center fully determines how far the palindrome can grow.

Palindromes like "bb" have a center between two characters.

Expand around center.

Tags

• dsa
• data structures and algorithms
• strings
• expand around center
• medium
• interview preparation