‹ DS&A interview · Socratic
DSA · Dynamic Programming / Strings · #133

Palindromic Substrings

Module 78 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given a string `s`, return the number of **palindromic substrings** in it. A string is a palindrome when it reads the same forward and backward. A **substring** is a contiguous sequence of characters within the string. Substrings that occur at different start/end positions are counted separately, even if they consist of the same characters. Implement the function `countSubstrings(s)` that returns the total count as a number.

Examples
  • s = "abc" → 3 — The palindromic substrings are "a", "b", "c".
  • s = "aaa" → 6 — The palindromic substrings are "a", "a", "a", "aa", "aa", "aaa".
  • s = "abba" → 6 — "a", "b", "b", "a", "bb", "abba".
Constraints
  • · 1 <= s.length <= 1000
  • · s consists of lowercase English letters.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.