LESSON 227 OF 348 · TWO POINTERS

Palindrome Substrings in TypeScript: Checking Every Substring in O(n³)

Practice O(n³) 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 they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]

STEP 1 OF 10

Guided

Ctrl + Enter to check

TYPESCRIPT · TWO POINTERS

Palindrome Substrings in TypeScript, explained

Problem overview

The method countPalindromes receives a string, input, and returns how many of its contiguous substrings are palindromes. Substrings with different start or end indices are counted separately, even when they hold the same characters.

For "abbcbc" the answer is 9. The six single characters are palindromes. So are "bb" (indices 1 to 2), "bcb" (indices 2 to 4) and "cbc" (indices 3 to 5). The single "b" at index 1 and the one at index 2 are two substrings, since their positions differ, and both are counted.

Approach: try every substring and test it

A substring is fixed by its start index i and its end index j, with i <= j. A string of length n has n * (n + 1) / 2 of them. The direct plan is to loop over all pairs (i, j), test each substring, and count the ones that pass.

The test is the two-pointer palindrome check. One pointer starts at i and the other at j. While the left one is before the right one, the characters they point to must be equal, and then both pointers move inward. A mismatch means the substring isn't a palindrome.

The test works on the indices i and j of the original string, so it never builds the substring itself. That avoids copying characters for every pair.

This is the simplest correct approach. Its cost grows quickly with the length of the string, and the next lesson on this problem counts the same palindromes by expanding outward from each center, which is faster.

Counting by start index shows the loops at work on "abbcbc":

i = 0: "a"                  -> 1
i = 1: "b", "bb"            -> 2
i = 2: "b", "bcb"           -> 2
i = 3: "c", "cbc"           -> 2
i = 4: "b"                  -> 1
i = 5: "c"                  -> 1

The sum is 9. For each start, the inner loop also tries the longer substrings, such as "bbc" or "bcbc", but they fail the test and add nothing.

Step by step

Declare result as 0. It is the running count of palindromes.
Loop i over the indices of input. It is the start of the substring.
Loop j from i to the last index. It is the end of the substring. Starting at i makes the one-character substring input[i] the first one tried.
Call this.isPalindrome(input, i, j), and when it returns true, add 1 to result. The lesson assumes the helper exists and writes it afterwards.
Return result when both loops are done.
Declare isPalindrome with the string and the two indices left and right, returning a boolean.
Loop while left < right. The pointers walk toward the middle, and the loop ends when they meet or cross.
Return false on a mismatch: if input[left] !== input[right], the substring can't be a palindrome.
Move the pointers: left++ and right--.
Return true after the loop. Every pair matched.

The solution in TypeScript

class Solution {
    isPalindrome(input: string, left: number, right: number): boolean {
        while (left < right) {
            if (input[left] !== input[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    countPalindromes(input: string): number {
        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;
    }
}

The TypeScript details worth knowing:

Parameters can be changed. isPalindrome moves left and right directly. They are local copies, since numbers are passed by value, so the loop variables i and j in the caller are untouched.
Calling a method with this. Inside the class, isPalindrome is a method of the object, so the call is this.isPalindrome(...). The method appears before countPalindromes in the class, but the order doesn't matter for methods.
Strings can be indexed. input[left] is a one-character string, and !== compares two such strings by content.
Types are only for the compiler. The annotations are removed when TypeScript is compiled to JavaScript, so they don't add any work at run time.

Complexity

Time: O(n³). There are about n²/2 pairs (i, j). For each pair, isPalindrome compares at most half of the substring, which is up to n / 2 steps. The worst case is a string of identical characters, where every test runs to the end. For most strings, tests stop early at the first mismatch, but the bound has to cover the worst case.

Space: O(1). The code uses a few numbers and no extra arrays or substrings.

Edge cases and common mistakes

Empty string. The loops never run and the result is 0.
All different characters. "abc" gives 3: only the single characters are palindromes.
All the same character. "aaa" gives 6: three single characters, two of length 2 and one of length 3. Every substring counts.
Starting j at i + 1. That skips the single-character substrings, so the count would be too low by n.
Counting distinct palindromes. The problem counts positions, not distinct strings. In "abbcbc" the two single "b" substrings both count.
Building substrings. Calling slice for every pair, then reversing and comparing, gives the right answer but copies characters for every pair. Working with indices avoids that.

Testing

"abbcbc" gives 9.
"abc" gives 3.
"aaa" gives 6.
"" gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free