49. Longest Palindromic Audio Fragment

Problem

An audio-pipeline debugging tool represents a short window of quantized audio tokens (e.g. codebook/feature ids, mapped to characters for the sake of this exercise) as a string. A symmetric run of tokens can indicate a looping artifact or padded silence, so the tool scans for the longest palindromic fragment in the window.

Return the longest contiguous palindromic substring of tokens. If there are multiple of the same maximum length, return the first one found scanning left to right by increasing length.

Source: src/49_longest_palindromic_audio_fragment.py

def longest_palindromic_fragment(tokens: str) -> str:

>>> longest_palindromic_fragment("babad")
'bab'

>>> longest_palindromic_fragment("cbbd")
'bb'

Step-by-Step Approach

1. Define dp[i][j] as True iff tokens[i:j+1] is a palindrome. Every single character is trivially a palindrome, so dp[i][i] = True for all i.
2. Build up by increasing substring length, since a length-L span's palindrome status depends on the length-(L-2) span nested inside it.
3. For a candidate span tokens[i:j+1]: it's a palindrome iff its endpoints match (tokens[i] == tokens[j]) and the inner span tokens[i+1:j] is also a palindrome (or the span is short enough that there's no meaningful inner span to check, i.e. length 1 or 2).
4. Track the best (start, max_len) seen so far, updating only on strict improvement so the first-found tie wins.
5. After filling the table, slice out tokens[start:start + max_len] as the answer.
6. Handle the empty-string edge case up front, since the DP table construction assumes at least one character.

The key insight is that palindrome-ness is naturally recursive on the inner substring, which is exactly the "optimal substructure" that makes bottom-up DP (filling shorter spans before longer ones) both correct and efficient at O(n²) time.

Reference solution

def longest_palindromic_fragment(tokens: str) -> str:
    n = len(tokens)
    if n == 0:
        return ""

    # dp[i][j] = True iff tokens[i:j+1] is a palindrome; O(n^2) time, O(n^2) space
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True  # every single character is a palindrome of length 1

    # build up by increasing substring length so dp[i+1][j-1] is already known
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if tokens[i] == tokens[j]:
                # length 2 needs no inner check; longer needs the inner span to be a palindrome too
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start, max_len = i, length

    return tokens[start:start + max_len]

Key Functions & Tricks

• dp[i][j] 2D table — caches whether every substring is a palindrome so longer spans reuse shorter spans' results instead of re-checking from scratch.
• Length-ascending iteration order — guarantees dp[i+1][j-1] is already computed before it's needed for the length-L span.
• length == 2 or dp[i + 1][j - 1] — the base-case short-circuit that avoids indexing an empty or invalid inner span.
• Strict improvement check (length > max_len, not >=) — guarantees ties resolve to the first (leftmost, shortest-length-found-first) match.
• tokens[start:start + max_len] — final slice extraction using the tracked best span.

How to Recognize This Pattern