Skip to main content

21. Palindromic Substrings

mediumAsked at Intuit

Count the number of palindromic substrings in a string. Intuit asks this as a string-DP warm-up and to probe whether you can pick the right expansion approach over the obvious DP table.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit onsite — string-DP round, candidate noted expand-around-center was preferred.
  • LeetCode Discuss (2025-11)— TurboTax SWE intern phone screen, palindrome count variant.

Problem

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Examples

Example 1

Input
s = "abc"
Output
3

Explanation: Three palindromes: 'a', 'b', 'c'.

Example 2

Input
s = "aaa"
Output
6

Explanation: Palindromes: 'a','a','a','aa','aa','aaa'.

Approaches

1. Brute force check every substring

Enumerate all O(n^2) substrings and check if each is a palindrome.

Time
O(n^3)
Space
O(1)
function countSubstrings(s) {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j + 1);
      if (sub === sub.split('').reverse().join('')) count++;
    }
  }
  return count;
}

Tradeoff: Cubic — fine to mention but slow on n=1000.

2. Expand around center (optimal)

For each potential center (each char for odd-length, each gap for even-length), expand outward while characters match. Each successful expansion is one palindrome.

Time
O(n^2)
Space
O(1)
function countSubstrings(s) {
  let count = 0;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      count++;
      l--;
      r++;
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd-length, center at i
    expand(i, i + 1); // even-length, center between i and i+1
  }
  return count;
}

Tradeoff: Quadratic time, constant space. Cleaner than DP for counting; DP wins if you also need to return the substrings themselves.

Intuit-specific tips

Intuit interviewers grade for whether you reach for expand-around-center over a 2D DP table — both are O(n^2) time but expand uses O(1) space. They probe whether you remember both odd-length and even-length centers (a common mistake). Bonus signal: mention Manacher's algorithm reaches O(n) but the implementation complexity isn't worth it under n=1000.

Common mistakes

  • Only checking odd-length centers and missing even-length palindromes like 'aa'.
  • Allocating a 2D DP table when expand-around-center uses O(1) space.
  • Off-by-one in the while-loop bounds (l >= 0 and r < n).

Follow-up questions

An interviewer at Intuit may pivot to one of these next:

  • Longest Palindromic Substring — return the substring itself (LC 5).
  • Longest Palindromic Subsequence — characters need not be contiguous (LC 516).
  • Implement Manacher's algorithm for O(n) palindrome detection.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why two expansion calls per index?

Odd-length palindromes have a single-char center (expand(i, i)); even-length palindromes have a two-char center (expand(i, i+1)). Missing the even case is the most common bug.

When would I prefer the DP table over expand-around-center?

When you need to query 'is s[i..j] a palindrome?' many times, or when you need to reconstruct all palindromic substrings. The DP gives O(1) lookup; expand-around-center recomputes.

Practice these live with InterviewChamp.AI

Drill Palindromic Substrings and other Intuit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →