647. Palindromic Substrings

Palindromic Substrings (LeetCode 647) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Expanding From Center (Palindromes) subpattern.

How to solve Palindromic Substrings

Palindromic Substrings is a Expanding From Center problem, part of Two Pointers. Master the expand from center technique for finding palindromic substrings and longest palindrome problems.

Work towards the solution in these steps:

  1. How can we reuse a previously computed palindrome to compute a larger palindrome?
  2. If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
  3. Complexity based hint:</br> 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?

The reference solution runs in O(n) time and O(n) space.

The Palindromic Substrings solution and editorial walks through the full approach with reference code.

Problem statement

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.

Topics and companies

Topics: Two Pointers, String, Dynamic Programming.

Reported in interviews at Facebook, Goldman Sachs, Expedia, Google, Twitter, Microsoft, Bloomberg, Docusign.

How to practise Palindromic Substrings on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Palindromic Substrings in the code editor, or read the Palindromic Substrings editorial for a worked solution with its approach and complexity analysis.

Where Palindromic Substrings sits in the DSA pattern sheet

Problems related to Palindromic Substrings

Other problems that use the same Expanding From Center (Palindromes) and Two Pointers techniques:

Palindromic Substrings FAQ

What is the LeetCode number of Palindromic Substrings?

Palindromic Substrings is LeetCode problem 647, rated Medium.

What pattern is used to solve Palindromic Substrings?

Palindromic Substrings is a Expanding From Center problem. It belongs to the Two Pointers pattern, in the Expanding From Center (Palindromes) subpattern.

What is the time complexity of Palindromic Substrings?

The reference solution runs in O(n) time and O(n) space.

Which companies ask Palindromic Substrings?

Palindromic Substrings has been reported in interviews at Facebook, Goldman Sachs, Expedia, Google, Twitter, Microsoft, Bloomberg, Docusign.

Preparing this workspace.