Palindromic Substrings

Palindromic Substrings 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.

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

• Two Pointers pattern guide
• Expanding From Center (Palindromes) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Palindromic Substrings

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

• Longest Palindromic Substring — Medium, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern
• Crawler Log Folder — Easy, same pattern
• Delete the Middle Node of a Linked List — Medium, same pattern