Start learning free

LESSON 246 OF 410 · TWO POINTERS

Palindrome Substrings in JavaScript: Brute Force Count

Practice O(n3) Read the full explanation

Given a string, count the number of palindromic contiguous substrings in the string.

The substrings with different start indexes or end indexes are counted as different substrings even if they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]
STEP 1 OF 7
    Ctrl + Enter to check

    JAVASCRIPT · TWO POINTERS

    Palindrome Substrings in JavaScript, explained

    Problem overview

    The method countPalindromes(input) receives a string and returns how many of its contiguous substrings are palindromes. A palindrome reads the same forwards and backwards, such as "bcb". Substrings are counted by position, not by content: if the same text appears at two different places, it counts twice. In "abbcbc" the answer is 9:

    a  b  b  c  b  c    (6 single characters)
bb                  (indices 1 to 2)
bcb                 (indices 2 to 4)
cbc                 (indices 3 to 5)

    Every single character is a palindrome, so a string of length n always scores at least n. For "abc" the answer is exactly 3, for "aaa" it is 6 (three single letters, two "aa" and one "aaa"), and for the empty string it is 0.

    Approach: check every substring

    The lesson takes the direct route. A substring is fixed by its start index i and its end index j, with i <= j. Two nested loops visit every such pair exactly once. For each pair, a helper decides whether the text between i and j is a palindrome, and when it is, the count goes up by one.

    A string of length n has n * (n + 1) / 2 substrings: 21 for the 6 characters of "abbcbc", and 500,500 for a string of 1,000 characters. Checking each one costs time proportional to its length, so the total grows with the cube of n. That is fine for short strings and slow for long ones. A faster way, which grows palindromes outwards from each possible centre in O(n²), is the subject of the next lesson on this problem. This one practises the plain version first.

    Step by step

    1. Start a counter. result is declared with let and set to 0. Every palindromic substring adds exactly one.
    2. Loop over start indices. i runs from 0 up to, but not including, input.length.
    3. Loop over end indices. j starts at i, not at 0, so that each substring is visited once. Starting at i also means j == i is the single-character case, which is always a palindrome.
    4. Test and count. If this.isPalindrome(input, i, j) is true, increment result. Because the helper is a method of the class, the call goes through this.
    5. Return the counter after both loops finish.
    6. Write the helper isPalindrome(input, left, right). Both indices are inclusive.
    7. Cut out the substring. input.substring(left, right + 1) takes the characters from left up to but not including its second argument, so the end needs the + 1.
    8. Reverse it. JavaScript strings have no reverse method, but arrays do. So split("") turns the string into an array of characters, reverse() reverses that array, and join("") glues it back into a string.
    9. Compare the substring with its reversed copy and return the result of first == second.

    The solution in JavaScript

    class Solution {
    isPalindrome(input, left, right) {
        let first = input.substring(left, right + 1);
        let second = first.split("").reverse().join("");
        return first == second;
    }
    countPalindromes(input) {
        let result = 0;
        for (let i = 0; i < input.length; i++) {
            for (let j = i; j < input.length; j++) {
                if (this.isPalindrome(input, i, j)) {
                    result++;
                }
            }
        }
        return result;
    }
}

    Details worth knowing:

    • substring takes an exclusive end. "abc".substring(0, 2) is "ab". That is why the helper uses right + 1 while the loops treat j as an inclusive index.
    • reverse() changes the array it is called on. That is harmless here, because split("") creates a fresh array on every call. The string first is never changed, since strings in JavaScript are immutable.
    • split("") splits into UTF-16 code units. For ordinary letters this is the same as characters. For emoji and some other symbols, which take two code units, reversing would scramble the pair. The lesson's inputs are plain text, so this does not matter here.
    • Comparison is case-sensitive. "Aa" has two palindromes, its two single letters, because "Aa" reversed is "aA", which is a different string.

    Complexity

    There are about n² / 2 substrings, and for each one the helper copies, splits, reverses and joins up to n characters. The time is O(n³). The extra space is O(n), for the temporary substring and array built inside one call of the helper; they are discarded after each call.

    The cost can be reduced without changing the idea. Comparing characters from both ends inwards with two indices needs no copies and stops at the first mismatch, but the worst case, a string of one repeated letter, is still O(n³). Growing palindromes outwards from each centre brings it down to O(n²) in the worst case.

    Edge cases and common mistakes

    • Forgetting the single characters. The inner loop must start at i, not i + 1, or the n one-letter palindromes are lost. "abc" would give 0 instead of 3.
    • Off-by-one in substring. Using input.substring(left, right) drops the last character, so every single-character substring becomes the empty string, which counts as a palindrome. The code still runs but checks the wrong text, and the count is wrong.
    • Counting distinct palindromes. The problem counts positions. In "aaa", "a" appears three times and counts three times, which gives 6 in total. A Set of texts would give 3.
    • Calling the helper without this. Inside a class method, isPalindrome(...) by itself is looked up as a variable and fails with a ReferenceError. Write this.isPalindrome(...).
    • Empty input. The outer loop does not run, so the result is 0.

    Testing

    Try these in the editor:

    • "abbcbc" returns 9.
    • "aaa" returns 6.
    • "abc" returns 3.
    • "abba" returns 6.
    • "racecar" returns 10.
    • "" returns 0.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free