Palindromic Substrings Leetcode Problem 647 [Python Solution]

On the Palindromic Substrings LeetCode problem, we’ll start with a basic overview of the problem, then delve into a brute-force approach before optimizing it.

By the end of this journey, you’ll have a clear understanding of how to count palindromic substrings efficiently using Python.

Problem Overview

Palindromic Substrings LeetCode Problem:

Given a string s, your task is to return the number of palindromic substrings within it.

A string is considered a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Let’s illustrate this problem with an example.

Example 1:

Input: s = “abc”

Output: 3

Explanation: Three palindromic substrings: “a”, “b”, “c”.

Example 2:

Input: s = “aaa”

Output: 6

Explanation: Six palindromic substrings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Now, let’s break down the problem and understand the constraints it presents.

Understanding Palindromic Constraints

Before we jump into coding, it’s essential to grasp a few key concepts regarding palindromes.

Palindromes come in two primary flavors: even and odd.

Even Palindromes: These are palindromes with an even number of characters.

For example, “abba” or “noon.”

Odd Palindromes: These are palindromes with an odd number of characters.

For example, “aba” or “madam.”

When counting palindromic substrings, we need to account for both even and odd-length palindromes.

Let’s explore the constraints and the problem-solving approach.

Edge Cases a Valid Solution Must Consider

In any coding problem, you need to consider edge cases to ensure your solution handles all scenarios.

Here are some of the edge cases for the Palindromic Substrings problem:

Empty String: What if the input string is empty?

It should be considered a valid scenario.

String with a Single Character: When the input string contains only one character, it’s a valid palindrome by itself.
String with No Palindromes: There might be cases where the input string contains no palindromic substrings.

Your solution should return the appropriate count in such scenarios.

With these considerations in mind, let’s dive into solving the problem.

Palindromic Substrings LeetCode Problem Solution

1. Bruteforce Approach

The initial approach to solve this problem is through brute force.

We’ll traverse the string, and for each character, we’ll expand in both directions to identify palindromic substrings.

Here’s the Python code for this approach:

View on GitHub ➹

def countSubstrings(self, s: str) -&gt; int:
    res = 0

    for i in range(len(s)):
        res += self.countPali(s, i, i)  # Odd length palindromes
        res += self.countPali(s, i, i + 1)  # Even length palindromes
    return res

def countPali(self, s, l, r):
    res = 0
    while l &gt;= 0 and r &lt; len(s) and s[l] == s[r]:
        res += 1
        l -= 1
        r += 1
    return res

In the code above, we start by initializing a variable res to count the palindromic substrings.

Then, we loop through the string s.

For each character in the string, we call the countPali function twice.

The first call checks for palindromes with odd lengths, using the same character as the center.
The second call checks for palindromes with even lengths, with two characters as the center.

The countPali function is responsible for expanding outwards from the center position and counting the palindromic substrings.

If the characters match, we increment the count res.

This approach allows us to find both odd and even length palindromes efficiently.

Now, let’s discuss the time and space complexity of this solution.

Time and Space Complexity

Time Complexity

The time complexity of this solution is O(N^2), where N is the length of the input string s.

This is because we traverse the string and, for each character, expand in both directions to find palindromic substrings.

In the worst case, we can have N characters as centers, resulting in N^2 iterations.

Space Complexity

The space complexity of this solution is O(1) since we are using a constant amount of extra space to store variables and intermediate results.

We do not rely on additional data structures that grow with the input size.

Reasoning Behind Our Approach

Our approach efficiently solves the problem by considering both odd and even length palindromes.

It eliminates repeated work by starting from the middle of each potential palindrome and expanding outwards.

This approach leads to a time complexity of O(N^2), which is acceptable for the given constraints.

In summary, the Palindromic Substrings problem involves counting the number of palindromic substrings in a given string.

We discussed a brute-force approach, along with Python code, to solve the problem efficiently.

We also explored the time and space complexity of the solution.

In the world of coding, it’s essential to tackle problems step by step, optimize where possible, and understand the underlying logic.

By doing so, you can develop efficient and effective solutions to a wide range of coding challenges.

Happy coding, and may your coding adventures be full of success!

If you have any questions or suggestions, please feel free to comment, ask, or share your thoughts.

Your feedback is highly valuable!

For more details and to access the LeetCode problem, you can visit the following link:

Palindromic Substrings LeetCode Problem

Thanks for reading and happy coding!