Data Structures and Algorithms (DSA)  

Longest Palindromic Substring – DSA Interview Question

Introduction

The Longest Palindromic Substring problem is one of the most frequently asked DSA interview questions in string algorithms. It checks your understanding of string traversal, symmetry, and optimization techniques.

In simple words, this problem asks you to find the longest part of a string that reads the same forward and backward.

This article explains the problem in plain language, with clear examples and an optimized solution commonly expected in interviews.

What is a Palindrome?

A palindrome is a word or string that remains the same when reversed.

This means:

  • The first character matches the last character

  • The second character matches the second last character

  • And so on

Examples of Palindromes

  • "madam"

  • "level"

  • "racecar"

  • "aa"

What is the Longest Palindromic Substring Problem?

You are given a string. Your task is to identify the longest palindrome.

Important points:

  • The substring must be continuous

  • There can be more than one palindrome, but you return the longest one

Example

Input:  "babad"
Output: "bab"

Explanation

  • "bab" is a palindrome

  • "aba" is also a palindrome

  • Both have the same length, so returning either one is acceptable

Brute Force Approach (Easy but Slow)

In the brute-force approach, we check all possible substrings and verify whether each one is a palindrome.

Problems with Brute Force

  • Too many substrings

  • Checking palindrome repeatedly is costly

  • Time Complexity becomes O(n³)

This approach is not suitable for interviews.

Optimized Approach: Expand Around Center

The most commonly expected solution in interviews is the Expand Around Center approach.

Key Idea

  • Every palindrome expands from its center

  • A center can be:

    • One character (odd-length palindrome)

    • Two characters (even-length palindrome)

We try to expand around each possible center.

Step-by-Step Explanation

Steps:

  1. Start from each character in the string

  2. Treat it as the center of a palindrome

  3. Expand left and right while characters match

  4. Repeat the process for two-character centers

  5. Track the longest palindrome found

This approach avoids unnecessary checks.

Dry Run Example

String: "babad"

Centers and palindromes:

  • Center at index 1 → "bab"

  • Center at index 2 → "aba"

Longest length found = 3

Code Implementation

C++ Code

string longestPalindrome(string s) {
    int start = 0, maxLength = 1;

    for (int i = 0; i < s.length(); i++) {
        // Odd length palindrome
        int left = i, right = i;
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }

        // Even length palindrome
        left = i;
        right = i + 1;
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }
    }
    return s.substr(start, maxLength);
}

Java Code

public String longestPalindrome(String s) {
    int start = 0, maxLength = 1;

    for (int i = 0; i < s.length(); i++) {
        // Odd length
        int left = i, right = i;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }

        // Even length
        left = i;
        right = i + 1;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }
    }
    return s.substring(start, start + maxLength);
}

Python Code

def longestPalindrome(s):
    start = 0
    max_length = 1

    for i in range(len(s)):
        # Odd length
        left = right = i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > max_length:
                start = left
                max_length = right - left + 1
            left -= 1
            right += 1

        # Even length
        left = i
        right = i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > max_length:
                start = left
                max_length = right - left + 1
            left -= 1
            right += 1

    return s[start:start + max_length]

Time and Space Complexity

  • Time Complexity: O(n²)

  • Space Complexity: O(1)

This is efficient and acceptable for interviews.

Edge Cases to Consider

  • Empty string

  • String with one character

  • All characters are the same

These cases should always be tested.

Common Interview Variations

  • Count palindromic substrings

  • Longest palindromic subsequence

  • Check if a string is a palindrome

These variations are often asked as follow-up questions.

Summary

The Longest Palindromic Substring problem is a classic string-based DSA question that teaches how symmetry can be used to optimize solutions. By expanding around possible centers, we can find the longest palindrome efficiently without checking all substrings. This approach is simple, interview-friendly, and widely accepted, making it an essential problem for mastering string algorithms.

Membership not found