647. Palindromic Substrings LeetCode Solution

In this guide, you will get 647. Palindromic Substrings LeetCode Solution with the best time and space complexity. The solution to Palindromic Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Palindromic Substrings solution in C++
Palindromic Substrings solution in Java
Palindromic Substrings solution in Python
Additional Resources

647. Palindromic Substrings LeetCode Solution image

Problem Statement of Palindromic Substrings

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.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(1)

647. Palindromic Substrings LeetCode Solution in C++

class Solution {
 public:
  int countSubstrings(string s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      ans += extendPalindromes(s, i, i);
      ans += extendPalindromes(s, i, i + 1);
    }

    return ans;
  }

 private:
  int extendPalindromes(const string& s, int l, int r) {
    int count = 0;

    while (l >= 0 && r < s.length() && s[l] == s[r]) {
      ++count;
      --l;
      ++r;
    }

    return count;
  }
};
/* code provided by PROGIEZ */

647. Palindromic Substrings LeetCode Solution in Java

class Solution {
  public int countSubstrings(String s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      ans += extendPalindromes(s, i, i);
      ans += extendPalindromes(s, i, i + 1);
    }

    return ans;
  }

  private int extendPalindromes(final String s, int l, int r) {
    int count = 0;

    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
      ++count;
      --l;
      ++r;
    }

    return count;
  }
}
// code provided by PROGIEZ

647. Palindromic Substrings LeetCode Solution in Python

class Solution:
  def countSubstrings(self, s: str) -> int:
    def extendPalindromes(l: int, r: int) -> int:
      count = 0

      while l >= 0 and r < len(s) and s[l] == s[r]:
        count += 1
        l -= 1
        r += 1

      return count

    ans = 0

    for i in range(len(s)):
      ans += extendPalindromes(i, i)
      ans += extendPalindromes(i, i + 1)

    return ans
 # code by PROGIEZ