Longest Palindromic Substring

An interactive, step-by-step visualisation of Longest Palindromic Substring.

Category: Dynamic Programming
Time complexity: O(n²)
Space complexity: O(n²)

Pseudocode

dp[i][i] = true
dp[i][i+1] = (s[i]==s[i+1])
dp[i][j] = s[i]==s[j] and dp[i+1][j-1]
track the longest true span

Reference implementation

def longest_pal_substring(s):
    n = len(s); dp = [[False]*n for _ in range(n)]
    best = (0, 1)
    for i in range(n): dp[i][i] = True
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i]==s[j] and (length&lt;=2 or dp[i+1][j-1]):
                dp[i][j] = True; best = (i, length)
    i, length = best
    return s[i:i+length]

Open the interactive Longest Palindromic Substring visualisation →