Longest Palindromic Substring (Without DP)

Problem Statement❯

Given a string, your task is to find the longest palindromic substring present in it. A substring is a contiguous sequence of characters within the string, and a palindrome is a string that reads the same forward and backward.

Note: You must solve this problem without using Dynamic Programming (DP). Center expansion technique is allowed.

Examples❯

Input String	Longest Palindromic Substring	Description
"abaxyzzyxf"	xyzzyx	Longest palindrome in the middle
"babad"	bab	"bab" and "aba" are both valid; return any one
"cbbd"	bb	Longest even-length palindrome
"a"	a	Single character string is itself a palindrome
"ac"	a	No multi-letter palindrome, return any single character
"aaaa"	aaaa	All characters same, entire string is the palindrome
"abcde"	a	No repeated characters, return any single character
""		Empty string has no palindromic substring

Solution❯

Understanding the Problem

We are given a string and our goal is to find the longest substring within it that is also a palindrome. A palindrome is a sequence of characters that reads the same backward as forward. For example, in the string "babad", "bab" and "aba" are palindromes.

We are going to solve this problem using a method called center expansion. This means we pick a center point in the string and try to expand outwards to see if we can build a palindrome from there. This center can be a single character (for odd-length palindromes) or a pair of adjacent characters (for even-length palindromes).

Step-by-Step Solution with Example

Step 1: Pick each character as a potential center

For a string of length n, there are 2n - 1 possible centers: n individual characters (for odd-length palindromes) and n - 1 pairs of adjacent characters (for even-length palindromes).

Step 2: Expand around each center

For each center, expand outward as long as the characters on both sides are the same. This means we’re checking whether the substring formed is a palindrome.

Step 3: Track the longest palindrome found

Every time we find a palindrome longer than the current longest, we update our result to store its starting and ending indices.

Step 4: Apply the logic on an example: "babad"

Start at index 0, center is 'b'. Expand around: "b" → Not longer than current max (initialize with "b").
Index 1, center is 'a'. Expand: "aba" → It's a palindrome. Update result.
Index 2, center is 'b'. Expand: "bab" → Another palindrome of same length. We can keep the first or update to this.
Continue checking until end of string.

Final answer could be either "bab" or "aba".

Edge Cases

Case 1: Odd-length palindromes

Strings like "racecar" have a single character center. Our logic correctly handles these by expanding around one character.

Case 2: Even-length palindromes

For strings like "abba", our solution checks the center between two characters, allowing it to find such palindromes.

Case 3: Multiple valid answers

If there are multiple palindromes of the same length, such as in "babad", we can return any one of them as the problem allows that.

Case 4: No palindrome longer than 1

For strings like "abc", every single character is a palindrome. Our method will return any one of them.

Case 5: All characters are the same

In "aaaa", the whole string is a palindrome. Our expansion method will capture this correctly.

Case 6: Empty string

If input is "", return "" since there's nothing to search.

Finally

The center expansion technique is a simple yet powerful way to find the longest palindromic substring. It avoids complex dynamic programming setups and provides a time complexity of O(n²) and space complexity of O(1). By thinking about characters as centers and expanding outward, we can explore all palindromic possibilities effectively.

Algorithm Steps❯

Initialize two variables start and end to track the longest palindrome range.
For each index i in the string:
→ Expand around center with one character (odd-length).
→ Expand around center with two characters (even-length).
→ Update start and end if a longer palindrome is found.
Return the substring from start to end (inclusive).

Code

C++

Python

Java

Rust

Kotlin

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

char* longestPalindrome(char* s) {
    int n = strlen(s);
    static char res[1000];
    bool dp[n][n];
    memset(dp, false, sizeof(dp));

    int start = 0, maxLen = 1;
    for (int i = 0; i < n; i++) dp[i][i] = true;

    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i+1]) {
            dp[i][i+1] = true;
            start = i;
            maxLen = 2;
        }
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
                if (len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }
    strncpy(res, s + start, maxLen);
    res[maxLen] = '\0';
    return res;
}

int main() {
    char input[] = "babad";
    printf("Longest Palindromic Substring: %s\n", longestPalindrome(input));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	If the string is already a palindrome, each center will expand quickly and minimal comparisons are made.
Average Case	O(n^2)	Each character is treated as a center and expanded outward, leading to quadratic time in general.
Worst Case	O(n^2)	In the worst case, each expansion checks almost the entire string (e.g., for input like 'aaaaaaa').

Space Complexity❯

O(1)

Explanation: No extra space is used except for a few integer variables.

⬅ Previous TopicFind Longest Palindromic Substring - Dynamic Programming Approach

Next Topic ⮕Remove Outermost Parentheses in String

Comments

Loading comments...