Longest Palindromic Substring - Practice Coding Problems

Longest Palindromic Substring - Problem

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

A palindrome is a string that reads the same forward and backward. For example, "racecar" and "aba" are palindromes.

If there are multiple palindromic substrings of the same maximum length, return any one of them.

Input & Output

Example 1 — Basic Case

$ Input: s = "babad"

› Output: "bab"

💡 Note: Both "bab" and "aba" are valid palindromes of length 3. Either can be returned as they are both the longest.

Example 2 — Even Length Palindrome

$ Input: s = "cbbd"

› Output: "bb"

💡 Note: The longest palindromic substring is "bb" with length 2. Single characters are also palindromes but shorter.

Example 3 — Single Character

$ Input: s = "a"

› Output: "a"

💡 Note: A single character is always a palindrome, so return the entire string.

Constraints

1 ≤ s.length ≤ 1000
s consist of only digits and English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters to analyze

Process

Find all palindromic substrings and identify the longest

Output

Return the longest palindromic substring

Key Takeaway

🎯 Key Insight: Every palindrome has a center - expand outward from each possible center position to find all palindromes efficiently

Asked in

a Amazon 45 M Microsoft 38 G Google 32 A Apple 25

The key insight is that every palindrome has a center and expands symmetrically. The optimal expand around centers approach checks each position as a potential center and expands outward. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check every possible substring to see if it's a palindrome
Expand Around Centers	O(n²)	O(1)	Expand outward from each possible center to find palindromes
Dynamic Programming	O(n²)	O(n²)	Build a 2D table to track which substrings are palindromes

Brute Force — Algorithm Steps

Generate all possible substrings
For each substring, check if it's a palindrome
Keep track of the longest palindrome found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from the input

Check Palindrome

For each substring, verify if it reads the same forwards and backwards

Track Longest

Keep the longest palindrome found so far

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) return 0;
        start++;
        end--;
    }
    return 1;
}

char* solution(char* s) {
    int n = strlen(s);
    if (n == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    int maxLen = 0;
    int startIdx = 0;
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) {
                int len = j - i + 1;
                if (len > maxLen) {
                    maxLen = len;
                    startIdx = i;
                }
            }
        }
    }
    
    char* result = malloc(maxLen + 1);
    strncpy(result, s + startIdx, maxLen);
    result[maxLen] = '\0';
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) palindrome check for each

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track current and longest palindrome

✓ Linear Space

125.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler