Find Longest Palindromic Substring Without Dynamic Programming

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.

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.

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).

#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;
}

#include <iostream>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    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;
                start = i;
                maxLen = len;
            }
        }
    }
    return s.substr(start, maxLen);
}

int main() {
    string input = "babad";
    cout << "Longest Palindromic Substring: " << longestPalindrome(input) << endl;
    return 0;
}

def longest_palindrome(s):
    n = len(s)
    if n <= 1:
        return s

    dp = [[False]*n for _ in range(n)]
    start, max_len = 0, 1

    for i in range(n):
        dp[i][i] = True

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2

    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i+length-1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length

    return s[start:start+max_len]

input_str = "babad"
print("Longest Palindromic Substring:", longest_palindrome(input_str))

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;

    for (int i = 0; i < n; i++) dp[i][i] = true;

    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;
      }
    }

    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));
  }
}

function longestPalindrome(s) {
  const n = s.length;
  if (n <= 1) return s;

  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0, maxLen = 1;

  for (let i = 0; i < n; i++) dp[i][i] = true;

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

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      let j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

console.log("Longest Palindromic Substring:", longestPalindrome("babad"));

package main

import (
  "fmt"
)

func longestPalindrome(s string) string {
  n := len(s)
  if n <= 1 {
    return s
  }
  dp := make([][]bool, n)
  for i := range dp {
    dp[i] = make([]bool, n)
  }
  start, maxLen := 0, 1
  for i := 0; i < n; i++ {
    dp[i][i] = true
  }
  for i := 0; i < n-1; i++ {
    if s[i] == s[i+1] {
      dp[i][i+1] = true
      start, maxLen = i, 2
    }
  }
  for length := 3; length <= n; length++ {
    for i := 0; i <= n-length; i++ {
      j := i + length - 1
      if s[i] == s[j] && dp[i+1][j-1] {
        dp[i][j] = true
        if length > maxLen {
          start, maxLen = i, length
        }
      }
    }
  }
  return s[start : start+maxLen]
}

func main() {
  input := "babad"
  fmt.Println("Longest Palindromic Substring:", longestPalindrome(input))
}

fn longest_palindrome(s: &str) -> String {
    let n = s.len();
    let chars: Vec<char> = s.chars().collect();
    let mut dp = vec![vec![false; n]; n];
    let mut start = 0;
    let mut max_len = 1;

    for i in 0..n {
        dp[i][i] = true;
    }

    for i in 0..n - 1 {
        if chars[i] == chars[i + 1] {
            dp[i][i + 1] = true;
            start = i;
            max_len = 2;
        }
    }

    for len in 3..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            if chars[i] == chars[j] && dp[i + 1][j - 1] {
                dp[i][j] = true;
                if len > max_len {
                    start = i;
                    max_len = len;
                }
            }
        }
    }

    chars[start..start + max_len].iter().collect()
}

fn main() {
    let input = "babad";
    println!("Longest Palindromic Substring: {}", longest_palindrome(input));
}

fun longestPalindrome(s: String): String {
    val n = s.length
    if (n <= 1) return s

    val dp = Array(n) { BooleanArray(n) }
    var start = 0
    var maxLength = 1

    for (i in 0 until n) dp[i][i] = true

    for (i in 0 until n - 1) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true
            start = i
            maxLength = 2
        }
    }

    for (len in 3..n) {
        for (i in 0..n - len) {
            val j = i + len - 1
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true
                if (len > maxLength) {
                    start = i
                    maxLength = len
                }
            }
        }
    }

    return s.substring(start, start + maxLength)
}

fun main() {
    val input = "babad"
    println("Longest Palindromic Substring: ${longestPalindrome(input)}")
}

function longestPalindrome(s: string): string {
  const n = s.length;
  if (n <= 1) return s;

  const dp: boolean[][] = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0, maxLen = 1;

  for (let i = 0; i < n; i++) dp[i][i] = true;

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

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

console.log("Longest Palindromic Substring:", longestPalindrome("babad"));

Time complexity

Space complexity

O(1)

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