Palindromic Substrings - 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) {
    notification(`⚠️ <b>Important Note:</b> While this algorithm correctly counts all palindromic substrings, it does <b>not</b> have the optimal time complexity.  
        A more advanced approach called <b>Manacher’s Algorithm</b> can achieve <b>O(n)</b> time complexity</b> by using extra space.`);

    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const s = new VisArray(...inputS);
    let palindromeCount = 0;  
    makeVisVariable(palindromeCount).options({ label: 'palindromeCount' }).createVis();
    endBatch();

    // Function to expand around center and count palindromes
    function expandAroundCenter(left, right) {
        startPartialBatch();

        while (left >= 0 && right < s.length) {
            if (s[left] !== s[right]) {
                highlightIndices(s, [left, right], UNMATCH);
                notification(`❌ Mismatch: ${makeColoredSpan(`"${s[left]}"`, UNMATCH_COLOR)} ≠ ${makeColoredSpan(`"${s[right]}"`, UNMATCH_COLOR)}  
                    at indices ${left} and ${right}. Cannot expand this center any further, so we stop here.`);
                break;
            }

            // Found a valid palindrome
            highlightIndices(s, [left, right], MATCH);
            notification(`✅ Palindrome found: ${makeColoredSpan(`"${inputS.substring(left, right + 1)}"`, MATCH_COLOR)}  
                (indices ${left}…${right}). Counting this substring.`);
            palindromeCount += 1;
            left--;
            right++;
            highlightIndices(s, [left, right]);
        }
        
        notification(`📌 Done expanding around ${makeColoredSpan('this center', CURRENT_COLOR)} — no more palindromes can be extended from here.`);
        clearHighlights(s, left, right);
        endBatch();
    }

    for (let index = 0; index < s.length; index++) {
        startPartialBatch();
        highlightIndices(s, [index]);
        notification(`🎯 Processing index ${makeColoredSpan(index, CURRENT_COLOR)}.`);

        notification(`🔍 <b>Exploring odd-length palindromes by expanding around center:</b>  
            Using ${makeColoredSpan(`"${s[index]}"`, CURRENT_COLOR)} at index ${makeColoredSpan(index, CURRENT_COLOR)} as the <b>center</b> by passing it as both the initial <b>excluded-left</b> and <b>excluded-right</b> parameter to <code>expandAroundCenter</code>.`);
        expandAroundCenter(index, index); // Odd-length palindromes
        
        highlightIndices(s, [index, index + 1]);
        notification(`🔍 <b>Exploring even-length palindromes by expanding around center:</b>  
            Using indices ${makeColoredSpan(index, CURRENT_COLOR)} and ${makeColoredSpan(index + 1, CURRENT_COLOR)} as the initial <b>excluded-left</b> and <b>excluded-right</b> parameters of <code>expandAroundCenter</code>, treating them as the two sides of the <b>center</b>.`);
        expandAroundCenter(index, index + 1); // Even-length palindromes

        endBatch();
    }

    notification(`🏁 ${makeColoredSpan('Finished', MATCH_COLOR)} — counted a total of ${makeColoredSpan(palindromeCount, MATCH_COLOR)} palindromic substrings in the input.`);
    return palindromeCount;
}

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/>
        Each color in the visualization corresponds to a specific role in palindrome detection:<br/><br/>
        🟦 ${makeColoredSpan('Blue', CURRENT_COLOR)} → <b>Current center</b> (the character(s) being used as expansion center)<br/>
        🟩 ${makeColoredSpan('Green', MATCH_COLOR)} → <b>Matching characters</b> during expansion (valid palindrome segment)<br/>
        🟥 ${makeColoredSpan('Red', UNMATCH_COLOR)} → <b>Mismatched characters</b> that stop the current expansion<br/><br/>
        Together, these colors help track how each center expands and when the expansion stops.
    `);
}

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

Approach

We count all palindromic substrings in the input by treating each position in the string as either the center of a palindrome (for odd-length palindromes) or the left side of a two-character center (for even-length palindromes), and expanding outward from that center.

⚠️ Important Note: While this method correctly counts all palindromic substrings, it does not achieve the optimal time complexity. A more advanced approach, such as Manacher’s Algorithm, can perform the same task more efficiently by using extra space.

Key idea:
A palindrome reads the same forward and backward, so every palindrome is symmetric around some center. That center can be:
- A single character — for odd-length palindromes like "aba", centered on the middle letter.
- Between two characters — for even-length palindromes like "abba", centered between the two middle letters.
If two characters mirror each other as we expand outward from the center, they form a palindrome. Here, every valid palindrome we encounter counts toward the total (not just the longest one).
Expanding around a center:
We use a helper routine expandAroundCenter(left, right) to explore and count palindromes around a chosen center. For each center (for odd length we call it with left = i, right = i, for even length we call it with left = i, right = i + 1), it:
- Checks characters at left and right.
- If they match, that means s[left..right] is a palindrome, so we increment the global counter.
- Then we expand outward by doing left-- and right++ to see if we can grow this palindrome further.
- If they do not match (or we go out of bounds), expansion for this center stops — that center cannot produce any larger palindromes.
Odd-length and even-length palindromes:
For each index i in the string:
- Odd-length expansion: We call expandAroundCenter(i, i) and treat i as the center. This finds palindromes like "a", "aba", "racecar", etc.
- Even-length expansion: We call expandAroundCenter(i, i + 1) and treat i and i + 1 as the two sides of the center. This finds palindromes like "aa", "abba", etc.
  Note that we always call this even if s[i] !== s[i + 1] — the helper immediately stops in that case, which is fine.
We must do both calls for every i because palindromes can be either odd length or even length.
Counting palindromes:
We maintain a running counter palindromeCount. Every time expandAroundCenter sees that s[left] === s[right], it means s[left..right] is a valid palindromic substring, so we immediately increment palindromeCount. We do not store substrings, we just count them.
Result:
After we have expanded around every possible center in the string (both odd and even), palindromeCount holds the total number of palindromic substrings in the input, including duplicates and overlaps. That final count is returned.
Why this works:
Every palindromic substring has a well-defined center, and expanding outward from that center will enumerate it exactly once. By checking every possible center and expanding until the symmetry breaks, we are guaranteed to count all palindromic substrings.

Time Complexity

Let n be the length of the input string s. For each index i, we expand outward twice — once for odd-length palindromes and once for even-length palindromes. Each expansion can scan outward up to O(n) characters in the worst case, and we do this for all n indices. Therefore, the total running time is O(n²).

Space Complexity

The algorithm uses just a few variables. It does not allocate any data structures or recursive calls that scale with input size. Therefore, the auxiliary space usage is O(1).

Input-1

Palindromic Substrings - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity