Last updated on January 12th, 2025 at 03:51 am
Here, we see a Palindromic Substrings LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, String
Companies
Level of Question
Medium

Palindromic Substrings LeetCode Solution
Table of Contents
1. 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”.
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Expand Around Center”. This pattern is specifically designed to solve problems related to palindromic substrings or subsequences. The idea is to treat each character (and the space between characters) as the center of a potential palindrome and expand outward to check for palindromic properties.
3. Code Implementation in Different Languages
3.1 Palindromic Substrings C++
class Solution { public: int countSubstrings(string s) { int n = s.length(), ans = 0; for (int i = 0; i < n; ++i) { int even = palindromeCount(s, i, i + 1); int odd = palindromeCount(s, i, i); ans += even + odd; } return ans; } int palindromeCount(const string& s, int left, int right) { int count = 0; while (left >= 0 && right < s.length() && s[left] == s[right]) { --left; ++right; ++count; } return count; } };
3.2 Palindromic Substrings Java
class Solution { public int countSubstrings(String s) { int n = s.length(); int ans = 0; for(int i=0;i<n;i++) { int even = palindromeCount(s, i, i+1); int odd = palindromeCount(s, i-1, i+1); ans += even + odd + 1; } return ans; } public int palindromeCount(String s, int left, int right) { int count = 0; while(left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)) { count++; } return count; } }
3.3 Palindromic Substrings JavaScript
var countSubstrings = function(s) { const n = s.length; const palindrome = Array.from(Array(n), () => Array(n).fill(false)); let ans = 0; for (let i = 0; i < n; i++) { palindrome[i][i] = true; ans++; } for (let i = 0; i < n - 1; i++) { if (s[i] === s[i + 1]) { palindrome[i][i + 1] = true; ans++; } } for (let len = 3; len <= n; len++) { for (let i = 0; i < n - len + 1; i++) { if (s[i] === s[i + len - 1] && palindrome[i + 1][i + len - 2]) { palindrome[i][i + len - 1] = true; ans++; } } } return ans; };
3.4 Palindromic Substrings Python
class Solution(object): def countSubstrings(self, s): n, ans = len(s), 0 def palindromeCount(left, right): count = 0 while left >= 0 and right < n and s[left] == s[right]: left -= 1 right += 1 count += 1 return count for i in range(n): even = palindromeCount(i, i + 1) odd = palindromeCount(i, i) ans += even + odd return ans
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n²) | O(1) |
Java | O(n²) | O(1) |
JavaScript | O(n²) | O(n²) |
Python | O(n²) | O(1) |
where, n
is the length of the string
- The C++, Java, and Python implementations use the “Expand Around Center” approach, which is efficient in terms of space but has a quadratic time complexity.
- The JavaScript implementation uses a Dynamic Programming approach, which trades off space for potentially easier readability and reusability of intermediate results.
- The choice of approach depends on the constraints of the problem (e.g., memory limitations or input size).