Is Palindromic Substrings easy or hard?

Palindromic Substrings is rated Medium because the brute force idea is straightforward but recognizing the expand-around-center optimization requires pattern recognition. Candidates familiar with palindrome problems usually solve it quickly once they identify the center expansion strategy.

How to solve Palindromic Substrings in O(n)?

An O(n) solution exists using Manacher's Algorithm. It transforms the string and tracks palindrome radii while expanding symmetrically, avoiding repeated comparisons. Although linear time, it is complex and rarely required in interviews compared to the simpler O(n^2) center expansion approach.

What is the best approach for Palindromic Substrings?

The expand-around-center technique is the most practical solution. It treats every index and gap between indices as a potential palindrome center and expands outward while characters match. This approach runs in O(n^2) time with O(1) extra space and is the method most interviewers expect.

Is Palindromic Substrings asked at Google/Amazon/Meta?

Palindromic substring problems frequently appear in technical interviews at companies like Amazon, Google, and Meta because they test string manipulation, two-pointer reasoning, and dynamic programming fundamentals. Variants such as longest palindromic substring or palindrome partitioning are also common.

What data structure is used in Palindromic Substrings?

Most solutions rely on string traversal with two pointers expanding from a center. The dynamic programming approach uses a 2D boolean DP table where dp[i][j] represents whether substring s[i..j] is a palindrome. No advanced data structures are required.

What is the time complexity of Palindromic Substrings?

The optimal common solution runs in O(n^2) time using the expand-around-center technique. Dynamic programming also achieves O(n^2) time but requires O(n^2) space for the DP table. A naive brute force solution takes O(n^3) time because it checks every substring individually.

Palindromic Substrings Python or Java solution approach

In Python or Java, the typical implementation iterates through each index and expands around two centers: one for odd-length palindromes and one for even-length palindromes. Each expansion continues while characters match and increments the count. This results in O(n^2) time and O(1) space.

Description Hints 3 Solution Video 15:02

647. Palindromic Substrings

Medium73.2% acceptance25 companies

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.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

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

Asked at top 20 of 25 companies

Citadel Pure Storage Netskope Intuit Akamai BNY Mellon Meta Salesforce

IBM Walmart Labs PayPal Capital One

+8 more

Arista Networks HCLTech Epic Systems Oracle Goldman Sachs LinkedIn Anduril

Google

Topics

Hints open one at a time

Hint 1

How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2

If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3

Complexity based hint:
If we use brute force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?

15:02

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution