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.
- Blind 75 · #53 of 75 · 1-D Dynamic Programming
- NeetCode 150 · #104 of 150 · 1-D Dynamic Programming
- NeetCode 250 · #180 of 250 · 1-D Dynamic Programming
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:
- How can we reuse a previously computed palindrome to compute a larger palindrome?
- If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
- 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:
- 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
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.