Find Longest Palindromic Substring - Dynamic Programming

Given a string s, your task is to find the longest palindromic substring within it.

• A palindrome is a sequence of characters that reads the same forward and backward.
• Your goal is to return the longest continuous segment of the input string that forms a palindrome.

If multiple substrings of the same maximum length exist, you can return any one of them.

If the input string is empty, return an empty string.

Understanding the Problem

We are given a string, and we need to find the longest substring within it that is a palindrome. A palindrome is a sequence of characters that reads the same forward and backward, like "racecar" or "madam".

Our task is to locate the longest such sequence that appears continuously in the string.

This problem is ideal for dynamic programming, because we can build the answer for longer substrings using the answers for shorter ones.

Step-by-Step Solution with Example

Step 1: Define what we want to track

We will use a 2D table dp[i][j], where each cell tells us whether the substring from index i to j (inclusive) is a palindrome.

Step 2: Initialize all substrings of length 1

Every single character is a palindrome by itself. So we set dp[i][i] = true for all i.

Step 3: Handle substrings of length 2

These need special treatment because the general rule (checking the inside substring) doesn’t apply here. We simply check if s[i] == s[i+1]. If true, we set dp[i][i+1] = true.

Step 4: Fill the table for substrings of length ≥ 3

We use a nested loop to check all substrings from length 3 up to the full string. For each substring s[i..j], we check:

• If s[i] == s[j], and
• If dp[i+1][j-1] is true (the substring inside is already a palindrome)

If both are true, then s[i..j] is a palindrome and we set dp[i][j] = true.

Step 5: Keep track of the longest palindrome found

While filling the table, whenever we find a true in dp[i][j], we check if the length of this palindrome is longer than what we’ve seen so far. If it is, we update the starting index and length of the longest palindrome.

Step 6: Extract the result

After filling the table, we use the recorded start index and length to extract the longest palindromic substring from the original string and return it.

Example: Input = "babad"

Let’s apply our logic to the input "babad".

• Length 1 substrings: All set to true.
• Length 2 substrings: "ba", "ab", "ad" → none are palindromes.
• Length 3 substrings: "bab" and "aba" are palindromes.

So the longest palindromic substrings are "bab" and "aba". We return either.

Edge Cases

• Empty string: Return an empty string directly.
• All characters are the same: Example: "aaaa" → return the whole string as it is already a palindrome.
• No repeated characters: Example: "abc" → return any single character, since every single character is a palindrome.
• Multiple valid results: As in "babad", both "bab" and "aba" are valid. We can return either one.

Finally

This dynamic programming approach ensures we don’t repeat calculations. It gives us an efficient O(n²) solution, suitable for strings up to around 1000 characters.

By starting from the smallest substrings and building up, we make sure that when we check if s[i..j] is a palindrome, we already know whether the smaller parts are palindromes.

This method is beginner-friendly once you understand how dynamic programming builds upon smaller solutions.

1. Let n be the length of the input string s.
2. Create a 2D boolean array dp[n][n].
3. Every single character is a palindrome, so set dp[i][i] = true for all i.
4. Check all substrings of length 2 and mark dp[i][i+1] = true if s[i] == s[i+1].
5. For substrings longer than 2, set dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] == true.
6. Track the start index and max length of the longest palindrome found.
7. Return the substring using start index and max length.

#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(n^2)

We use a 2D boolean table to store whether substrings are palindromes.