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 <= 1000s consists of lowercase English letters.In this approach, consider each character in the string, and each pair of consecutive characters as the center of potential palindromes. From each center, expand outward until the substring is no longer a palindrome. This allows for both odd-length and even-length palindromes to be discovered.
The C solution uses two nested loops. The outer loop iterates over possible centers of palindromic substrings, which are twice the length of the string minus one (to account for centers in between characters for even-length palindromes). The inner loop expands from the center until a non-palindromic string is found.
C++
Java
Python
C#
JavaScript
Time complexity: O(n^2), where n is the length of the string.
Space complexity: O(1), since we're only using a few auxiliary variables.
Utilizing Dynamic Programming, we can store results of previously calculated palindromic substrings in a table. If we know a substring between two indices is a palindrome, we can extend this information to build larger palindromes, reducing redundant checks.
This C solution fills a DP table where dp[i][j] is true if the substring s[i..j] is a palindrome, using known results of smaller substrings to build the solution for larger substrings.
C++
Java
Python
C#
JavaScript
Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table.
| Approach | Complexity |
|---|---|
| Expand Around Center | Time complexity: O(n^2), where n is the length of the string. |
| Dynamic Programming | Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,124 views views
Watch 9 more video solutions →Practice Palindromic Substrings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor