Palindromic Substrings LeetCode Solution

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

Facebook

Level of Question

Medium

Palindromic Substrings LeetCode Solution

Palindromic Substrings LeetCode Solution

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.

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 ComplexitySpace Complexity
C++O(n²)O(1)
JavaO(n²)O(1)
JavaScriptO(n²)O(n²)
PythonO(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).
Scroll to Top