Largest Palindromic Substring (Without DP)

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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❯

To find the longest palindromic substring without using dynamic programming, we use a technique called center expansion. The idea is simple and intuitive: every palindrome is centered around a character (or between two characters), so we expand around each possible center and keep track of the longest one found.

Understanding Through Cases

Case 1: The palindrome has an odd length
Here, we consider each character as the center. For example, in the word racecar, the character 'e' is at the center of the palindrome. We expand both left and right from this center and compare characters to check if it forms a palindrome.

Case 2: The palindrome has an even length
Some palindromes are centered between two characters, like abba. In this case, we expand around the pair of equal characters and compare outward on both sides.

Case 3: Multiple palindromes
If there are multiple palindromic substrings of the same maximum length, we can return any one of them. For example, in babad, both "bab" and "aba" are valid answers.

Case 4: No palindromes longer than 1
If the string contains no repeated characters or palindromes, like abc, then each character is a palindrome of length 1. We can return any one of them.

Case 5: All characters are the same
In cases like aaaa, the entire string is a palindrome. Expanding from any center will eventually cover the whole string.

Case 6: Empty string
If the input string is empty, we return an empty string as there’s no palindromic substring to be found.

Why This Works

By checking for palindromes centered at every character (and between characters), we cover all possibilities. The approach avoids building a 2D table (used in DP), and runs efficiently in O(n²) time and O(1) space, which is optimal for a non-DP solution.

It’s a powerful technique that gives the correct answer without any complex setup—just repeated expansion and comparison.

Algorithm Steps❯

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

Code

Java
Python
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
public class LongestPalindromicSubstringDP {
  public static String longestPalindrome(String s) {
    int n = s.length();
    if (n <= 1) return s;

    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLength = 1;

    // All substrings of length 1 are palindromes
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // Check for substrings of length 2
    for (int i = 0; i < n - 1; i++) {
      if (s.charAt(i) == s.charAt(i + 1)) {
        dp[i][i + 1] = true;
        start = i;
        maxLength = 2;
      }
    }

    // Check substrings longer than 2
    for (int len = 3; len <= n; len++) {
      for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
          dp[i][j] = true;
          if (len > maxLength) {
            start = i;
            maxLength = len;
          }
        }
      }
    }
    return s.substring(start, start + maxLength);
  }

  public static void main(String[] args) {
    String input = "babad";
    System.out.println("Longest Palindromic Substring: " + longestPalindrome(input));
  }
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)If the string is already a palindrome, each center will expand quickly and minimal comparisons are made.
Average CaseO(n^2)Each character is treated as a center and expanded outward, leading to quadratic time in general.
Worst CaseO(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.