Longest Palindromic Substring - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const MATCH = 'match', MATCH_COLOR = 'green';
const UNMATCH = 'unmatch', UNMATCH_COLOR = 'red';

function visMainFunction(inputS) {
    initClassProperties();
    notification(`⚠️ <b>Important Note:</b> While this algorithm correctly finds the longest palindromic substring, it does <b>not</b> have the optimal time complexity.  
        A more efficient solution called <b>Manacher’s Algorithm</b> achieves better performance by using additional space.`);
    explanationAndColorSchemaNotifications();

    startBatch();
    const s = new VisArray(...inputS);
    let largestPalindromeStartIndex = 0, largestPalindromeIndexDiff = -1;
    makeVisVariable(largestPalindromeStartIndex).options({ label: 'largestPalindromeStartIndex' }).createVis();
    makeVisVariable(largestPalindromeIndexDiff).options({ label: 'largestPalindromeIndexDiff' }).createVis();
    endBatch();

    function expandAroundCenter(left, right) {
        startPartialBatch();

        while (left >= 0 && right < s.length) {
            if (s[left] !== s[right]) {
                highlightIndices(s, [left, right], UNMATCH);
                notification(`❌ <b>Mismatch:</b> "${s[left]}" ≠ "${s[right]}" at indices ${left} and ${right}. Stopping expansion for this center because the palindrome can’t grow further.`);
                break;
            }

            notification(`✅ <b>Match:</b> "${s[left]}" == "${s[right]}" at indices ${left} and ${right}. This is still a palindrome, so we expand outward (move left ↘ and right ↗).`);
            highlightIndices(s, [left, right], MATCH);

            left--;
            right++;
            highlightIndices(s, [left, right]);
        }
        endBatch();

        startPartialBatch();
        notification(`📌 <b>Largest palindrome found from this center:</b> "${inputS.substring(left + 1, right)}" (Indexes ${left + 1} to ${right - 1})`);
        clearHighlights(s, left, right);
        endBatch();

        return [left + 1, right - 1];
    }

    for (let index = 0; index < s.length; index++) {
        startPartialBatch();
        notification(`🎯 <b>Processing index:</b> ${index}`);

        highlightIndices(s, [index]);
        notification(`🔍 <b>Odd-length check:</b> Using "${s[index]}" at index ${index} as the center (e.g. looks for patterns like "aba").`);
        let [left, right] = expandAroundCenter(index, index);
        let diff = right - left;

        if (diff > largestPalindromeIndexDiff) {
            notification(`🏆 <b>Longest palindrome so far updated:</b> "${inputS.substring(left, right + 1)}" (indices ${left}…${right}).`);
            largestPalindromeStartIndex = left;
            largestPalindromeIndexDiff = diff;
        }

        highlightIndices(s, [index, index + 1]);
        notification(`🔍 <b>Even-length check:</b> Using indices ${index} and ${index + 1} as the center (looks for patterns like "abba").`);
        [left, right] = expandAroundCenter(index, index + 1);
        diff = right - left;

        if (diff > largestPalindromeIndexDiff) {
            notification(`🏆 <b>Longest palindrome so far updated:</b> "${inputS.substring(left, right + 1)}" (indices ${left}…${right}).`);
            largestPalindromeStartIndex = left;
            largestPalindromeIndexDiff = diff;
        }

        endBatch();
    }

    let result = inputS.substring(largestPalindromeStartIndex, largestPalindromeStartIndex + largestPalindromeIndexDiff + 1);
    notification(`🏁 <b>Finished:</b> The longest palindromic substring is "${result}". All possible centers have been checked.`);
    return result;
}

function highlightIndices(arr, indices, className = CURRENT) {
    startBatch();
    for (let index of indices) {
        if (index >= 0 && index < arr.length) {
            const visManager = arr.makeVisManagerForIndex(index);
            visManager.removeAllClasses();
            visManager.addClass(className);
        }
    }
    endBatch();
}

function clearHighlights(arr, start, end) {
    startBatch();
    for (let index = start; index <= end; index++) {
        if (index >= 0 && index < arr.length) {
            arr.makeVisManagerForIndex(index).removeAllClasses();
        }
    }
    endBatch();
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema:</b><br/>
        <span class='${CURRENT}' style='background:${CURRENT_COLOR};color:white;'>${CURRENT_COLOR} background</span> → 
        Highlights the <b>current indices</b> being considered during expansion around a center.<br/>
        <span class='${MATCH}' style='background:${MATCH_COLOR};color:black;'>${MATCH_COLOR} background</span> → 
        Marks <b>matching characters</b> that maintain the palindrome property during expansion.<br/>
        <span class='${UNMATCH}' style='background:${UNMATCH_COLOR};color:white;'>${UNMATCH_COLOR} background</span> → 
        Highlights <b>mismatched characters</b> where the palindrome expansion stops.
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, { backgroundColor: CURRENT_COLOR });
    setClassProperties(MATCH, { backgroundColor: MATCH_COLOR });
    setClassProperties(UNMATCH, { backgroundColor: UNMATCH_COLOR });
}

Approach

We find the longest palindromic substring by treating every position in the string as either the center of a palindrome (for odd-length cases) or the left side of a two-character center (for even-length cases), and expanding outward from the center.
⚠️ Important Note: While this algorithm correctly finds the longest palindromic substring, it does not have the optimal time complexity. A more efficient solution called Manacher’s Algorithm achieves better performance by using additional space.

Key idea:
A palindrome reads the same forward and backward, which means it is symmetric around a center. That center can be:
- One character — odd-length palindromes like "aba", centered at the middle letter.
- Between two characters — even-length palindromes like "abba", centered between two identical letters.
By expanding outward from the center while characters match, we can discover every palindrome in the string.
Expanding around center:
This step is handled by the expandAroundCenter helper, which explores the largest possible palindrome around a given center. For each center (for odd length called with left = i, right = i and for even length called with left = i, right = i + 1), it:
- Assumes that the given left and right pointers mark the exclusive boundaries of the current palindrome at the start of expansion.
- While both pointers are within bounds and s[left] === s[right], the substring s[left..right] is accepted as a valid palindrome by moving left and right outward.
- After expansion ends, since left and right represent the excluded boundaries, the helper returns the inclusive palindrome boundaries as [left + 1, right - 1].
Odd vs even palindromes:
For each index i:
- Odd-length check: Call expandAroundCenter(i, i), treating i as the center to find palindromes like "racecar".
- Even-length check: Call expandAroundCenter(i, i + 1), treating i as the first character of a two-character center to find palindromes like "noon". The helper treats these initial indices as exclusive boundaries, so there’s no need to check whether s[i] and s[i + 1] match before making the call.
Both checks are necessary because the longest palindrome could be either odd or even in length.
Tracking the best palindrome:
For each expansion, we maintain the variables below:
- largestPalindromeStartIndex → starting index of the current longest palindrome
- largestPalindromeIndexDiff → the difference between end and start indices of the current longest palindrome
If the current palindrome’s index difference (end - start) is larger than the recorded largestPalindromeIndexDiff, it means we’ve found a new longest palindrome so far, so both variables are updated accordingly. (Since the palindrome’s actual length is end - start + 1, a larger index difference always implies a longer palindrome.)
Result:
After testing all centers, the final answer is s.substring(largestPalindromeStartIndex, largestPalindromeStartIndex + largestPalindromeIndexDiff + 1), representing the longest palindromic substring in the input string.
Why this works:
Every palindrome must have a center. By expanding outward from every possible center and keeping the longest match, we are guaranteed to find the longest palindromic substring without redundant work.
Complexity:
There are O(n) centers (two per character: odd and even), and each expansion may take up to O(n). Hence, the total time complexity is O(n²), and the algorithm uses only O(1) extra space.

Time Complexity

Let n be the length of the input string s. For each index i, we try to expand a palindrome in two ways: treating i as the center (odd-length case) and treating i and i + 1 as the center (even-length case). Each such expansion can grow outward up to the full length of the string in the worst case.

There are O(n) possible centers, and each expansion can take up to O(n) in the worst case, so the total running time is O(n²).

Space Complexity

The algorithm uses a constant amount of extra state: a few indices (left, right, largestPalindromeStartIndex, largestPalindromeIndexDiff) and temporary values returned from expansion. It does not allocate any data structures or build a recursion tree that scales with input size. Therefore, the auxiliary space usage is O(1).

Input-1

Longest Palindromic Substring - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity