647. Palindromic Substrings (Medium)

Problem

Given a string s, return the number of palindromic substrings (counting duplicates).

Example

• s = "abc" → 3 (a, b, c)
• s = "aaa" → 6 (a, a, a, aa, aa, aaa)

LeetCode 647 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Brute force, check every substring

Python

def count_substrings(s):
    def is_pal(t):
        return t == t[::-1]          # L1: O(k) where k = len(t)
    count = 0
    for i in range(len(s)):          # L2: outer loop, n iterations
        for j in range(i, len(s)):   # L3: inner loop, up to n iterations
            if is_pal(s[i:j + 1]):   # L4: slice O(k) + reverse compare O(k)
                count += 1           # L5: O(1)
    return count

TypeScript

function countSubstrings(s: string): number {
    function isPal(t: string): boolean {
        return t === t.split('').reverse().join('');  // L1: O(k) reversal + compare
    }
    let count = 0;
    for (let i = 0; i < s.length; i++) {             // L2: outer loop, n iterations
        for (let j = i; j < s.length; j++) {         // L3: inner loop, up to n iterations
            if (isPal(s.slice(i, j + 1))) count++;   // L4/L5: slice + palindrome check
        }
    }
    return count;
}

Swift

final class Solution {
    func countSubstrings(_ s: String) -> Int { let c = Array(s); var count = 0; for i in c.indices { for j in i..<c.count { let part = Array(c[i...j]); if part == Array(part.reversed()) { count += 1 } } }; return count }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L2, L3 (nested loops)	$O(1)$	n² pairs	$O(n²)$
L4 (slice + palindrome check)	$O(k)$ per pair	n² pairs, avg k = n/2	$O(n³)$ ← dominates
L5 (increment)	$O(1)$	up to n²	$O(n²)$

The slice s[i:j+1] allocates a new string of length k, and the reverse comparison scans it again. Over all $O(n²)$ pairs the average substring length is $O(n)$, giving $O(n³)$ total.

Complexity

• Time: $O(n³)$, driven by L4 (slice + reverse per pair).
• Space: $O(n)$ per slice (the largest slice is the whole string).

Approach 2: Expand around center (canonical)

For each of 2n - 1 centers, expand outward and count every step that forms a palindrome.

Python

def count_substrings(s):
    def expand(l, r):
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:  # L1: O(1) per iteration
            count += 1                                   # L2: O(1)
            l -= 1                                       # L3: O(1)
            r += 1                                       # L4: O(1)
        return count

    return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))  # L5: 2n calls

TypeScript

function countSubstrings(s: string): number {
    function expand(l: number, r: number): number {
        let count = 0;
        while (l >= 0 && r < s.length && s[l] === s[r]) {  // L1: O(1) per iteration
            count++;                                          // L2: O(1)
            l--;                                             // L3: O(1)
            r++;                                             // L4: O(1)
        }
        return count;
    }
    let total = 0;
    for (let i = 0; i < s.length; i++) {
        total += expand(i, i) + expand(i, i + 1);           // L5: 2n calls
    }
    return total;
}

Swift

final class Solution {
    func countSubstrings(_ s: String) -> Int { let c = Array(s); var count = 0; func expand(_ a: Int, _ b: Int) { var l = a, r = b; while l >= 0 && r < c.count && c[l] == c[r] { count += 1; l -= 1; r += 1 } }; for i in c.indices { expand(i, i); expand(i, i + 1) }; return count }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L5 (loop over centers)	$O(1)$	2n - 1 centers	$O(n)$ calls
L1 (expand while condition)	$O(1)$	up to n per center	varies
L1-L4 (total expansion work)	$O(1)$ per step	$O(n)$ steps total	$O(n²)$ ← dominates
L2-L4 (count + advance)	$O(1)$	same as L1	$O(n²)$

Each character can be the turning point of at most $O(n)$ expansion steps, but summed across all 2n-1 centers the total expansion steps are bounded by $O(n²)$ in the worst case (e.g., “aaaa…”).

Complexity

• Time: $O(n²)$, driven by L1-L4 (expansion work summed across all centers).
• Space: $O(1)$ (no auxiliary structure; just two integer pointers).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: DP table

dp[i][j] = True iff s[i:j+1] is a palindrome. Fill by length; count the True entries.

Python

def count_substrings(s):
    n = len(s)                                           # L1: O(1)
    dp = [[False] * n for _ in range(n)]                 # L2: O(n²)
    count = 0
    for i in range(n):                                   # L3: base case, length-1
        dp[i][i] = True                                  # L4: O(1)
        count += 1                                       # L5: O(1)
    for length in range(2, n + 1):                       # L6: outer loop over lengths
        for i in range(n - length + 1):                  # L7: valid start positions
            j = i + length - 1                           # L8: O(1)
            if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):  # L9: O(1) lookup
                dp[i][j] = True                          # L10: O(1)
                count += 1                               # L11: O(1)
    return count

TypeScript

function countSubstrings(s: string): number {
    const n = s.length;                                          // L1: O(1)
    const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));  // L2: O(n²)
    let count = 0;
    for (let i = 0; i < n; i++) {                               // L3: base case, length-1
        dp[i][i] = true;                                        // L4: O(1)
        count++;                                                 // L5: O(1)
    }
    for (let length = 2; length <= n; length++) {               // L6: outer loop over lengths
        for (let i = 0; i <= n - length; i++) {                 // L7: valid start positions
            const j = i + length - 1;                           // L8: O(1)
            if (s[i] === s[j] && (length === 2 || dp[i + 1][j - 1])) {  // L9: O(1) lookup
                dp[i][j] = true;                                // L10: O(1)
                count++;                                         // L11: O(1)
            }
        }
    }
    return count;
}

Swift

final class Solution {
    func countSubstrings(_ s: String) -> Int { let c = Array(s), n = c.count; var dp = Array(repeating: Array(repeating: false, count: n), count: n), count = 0; for i in stride(from: n - 1, through: 0, by: -1) { for j in i..<n where c[i] == c[j] && (j - i < 2 || dp[i + 1][j - 1]) { dp[i][j] = true; count += 1 } }; return count }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L2 (allocate dp)	$O(n²)$	1	$O(n²)$
L3-L5 (base cases)	$O(1)$	n	$O(n)$
L6, L7 (nested loops)	$O(1)$	n(n-1)/2 pairs	$O(n²)$
L8-L11 (fill + count)	$O(1)$	$O(n²)$ pairs	$O(n²)$ ← dominates

Each cell is filled in $O(1)$ using a previously-computed shorter-length result. The outer loop sweeps lengths 2..n; the inner loop covers all valid start positions for that length, giving exactly n(n-1)/2 iterations total.

Complexity

• Time: $O(n²)$, driven by L6/L7/L8-L11 (the nested length-and-index loops).
• Space: $O(n²)$ for the dp table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
All substrings	$O(n³)$	$O(n)$
Expand around center	$O(n²)$	$O(1)$
DP table	$O(n²)$	$O(n²)$

Same pattern as problem 5. Manacher’s gives $O(n)$ if you need it.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_647.py and run.
# Uses the canonical implementation (Approach 2: expand around center).

def count_substrings(s):
    def expand(l, r):
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
        return count

    return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))

def _run_tests():
    assert count_substrings("abc") == 3    # LeetCode example 1: a, b, c
    assert count_substrings("aaa") == 6    # LeetCode example 2: a,a,a,aa,aa,aaa
    assert count_substrings("a") == 1      # single character
    assert count_substrings("aa") == 3     # a, a, aa
    assert count_substrings("abba") == 6   # a,b,b,a,bb,abba
    assert count_substrings("racecar") == 10  # r,a,c,e,c,a,r,aceca,cec,racecar
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function countSubstrings(s: string): number {
    function expand(l: number, r: number): number {
        let count = 0;
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            count++;
            l--;
            r++;
        }
        return count;
    }
    let total = 0;
    for (let i = 0; i < s.length; i++) {
        total += expand(i, i) + expand(i, i + 1);
    }
    return total;
}

console.assert(countSubstrings('abc') === 3);
console.assert(countSubstrings('aaa') === 6);
console.assert(countSubstrings('a') === 1);
console.assert(countSubstrings('aa') === 3);
console.assert(countSubstrings('abba') === 6);
console.assert(countSubstrings('racecar') === 10);
console.log('all tests pass');

Related data structures

• Strings, center-expansion

Related concepts

• Sequence DP, the prefix or position state pattern used for strings and ordered arrays.
• Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.