647. Palindromic Substrings

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (string palindromes) / expand around center
Difficulty: Medium
Companies: Google, Amazon, Meta, Apple, Uber
Frequency: High
LeetCode: 647

Problem (one-liner)

Count how many contiguous substrings of s are palindromes. Overlapping substrings are counted separately. Input: string s. Output: non-negative count.

Recognition Cues

“Count palindromic substrings”
Same expansion or DP table as longest palindrome, but accumulate count
Each character is a palindrome of length 1

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — every substring + check — O(n^3) time.
Better — 2D boolean table — O(n^2) time / O(n^2) space.
Optimal — expand from centers — O(n^2) time / O(1) extra space. <- pick this in interview.

Optimal Solution

Go

package main

func countSubstringsTable(s string) int {
	length := len(s)
	if length == 0 {
		return 0
	}
	table := make([][]bool, length)
	for index := range table {
		table[index] = make([]bool, length)
	}
	count := 0
	for end := 0; end < length; end++ {
		table[end][end] = true
		count++
		for start := 0; start < end; start++ {
			if s[start] == s[end] && (end-start < 2 || table[start+1][end-1]) {
				table[start][end] = true
				count++
			}
		}
	}
	return count
}

func countSubstrings(s string) int {
	length := len(s)
	if length == 0 {
		return 0
	}
	count := 0
	expand := func(left int, right int) {
		for left >= 0 && right < length && s[left] == s[right] {
			count++
			left--
			right++
		}
	}
	for center := 0; center < length; center++ {
		expand(center, center)
		expand(center, center+1)
	}
	return count
}

JavaScript

function countSubstringsTable(s) {
	const length = s.length;
	if (length === 0) return 0;
	const table = Array.from({ length }, () => new Array(length).fill(false));
	let count = 0;
	for (let end = 0; end < length; end++) {
		table[end][end] = true;
		count++;
		for (let start = 0; start < end; start++) {
			if (
				s[start] === s[end] &&
				(end - start < 2 || table[start + 1][end - 1])
			) {
				table[start][end] = true;
				count++;
			}
		}
	}
	return count;
}

function countSubstrings(s) {
	const length = s.length;
	if (length === 0) return 0;
	let count = 0;
	const expand = (left, right) => {
		while (left >= 0 && right < length && s[left] === s[right]) {
			count++;
			left--;
			right++;
		}
	};
	for (let center = 0; center < length; center++) {
		expand(center, center);
		expand(center, center + 1);
	}
	return count;
}