Palindromic Substrings

MEDIUM✓ CHIP-TIMEDLC #647 — FULL STATEMENT ↗

The drill: Count how many contiguous slices of a string are themselves palindromes — every single character counts as one.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string arrives, and the task is to count how many of its contiguous slices read the same forwards and backwards.

Two slices count separately even if they contain identical characters, as long as they start or end at different positions — this is a count of positions, not of distinct palindrome values.

Every single character on its own counts as a palindrome of length one, so the count is never zero for a non-empty string.

EX 01

s = "a"

→ 1

MINIMUM SIZE, ONE CHARACTER IS ONE PALINDROME

EX 02

s = "aaa"

→ 6

EVERY SUBSTRING OF A RUN OF THE SAME LETTER COUNTS

EX 03

s = "abc"

→ 3

NO REPEATS, ONLY SINGLE CHARACTERS COUNT

string length can run into the low thousands
count is by position, not by distinct palindrome text
every single character counts as its own palindrome
answer is one integer total

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

There are O(n^2) possible substrings, and checking each one for the palindrome property the naive way stacks another factor of n on top. What structure do palindromes share that skips the re-checking?

HINT 2 THE STRUCTURE

Every palindrome grows outward from a center — a character or a gap — and stops being one the moment its two ends stop matching. Counting from centers counts every palindrome exactly once.

HINT 3 ONE STEP FROM THE ANSWER

For each of the 2n-1 centers (n single characters, n-1 gaps), expand outward while both ends match and add one to the count on every successful expansion.

COACH'S BOARD — THE PATTERN, STEP BY STEP

COUNTING FROM EVERY CENTERPATTERN · EXPAND FROM EVERY CENTERs = "aba"

RUNNING COUNT

— empty —

STEP 1

Five centers to check in "aba": three characters and two gaps between them. Each successful expansion adds one to the count.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/palindromic-substrings.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)

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

        total = 0
        for i in range(n):
            total += expand(i, i)                # odd-length centers
            total += expand(i, i + 1)             # even-length centers
        return total

TIME O(N^2)SPACE O(1)PYTHON · RACE PACE · 17 LN

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        for i in range(n):
            for j in range(i, n):
                candidate = s[i:j + 1]
                if candidate == candidate[::-1]:
                    count += 1
        return count

TIME O(N^3)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += expand(s, i, i);
            total += expand(s, i, i + 1);
        }
        return total;
    }

    private int expand(String s, int l, int r) {
        int n = s.length();
        int count = 0;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
        return count;
    }
}

TIME O(N^2)SPACE O(1)JAVA · RACE PACE · 22 LN

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

TIME O(N^3)SPACE O(1)JAVA · TRAINING PACE · 25 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED