A LeetCode Daily Series — Day 69

Welcome! In this article, we will explore the fascinating problem of counting palindromic substrings in a given string. This problem is a great exercise for improving your string manipulation and algorithm design skills. We’ll walk through the problem step-by-step, explore different approaches, and understand their intricacies. Let’s dive in!

Palindromic Substrings - LeetCode leetcode.com

Can you solve this real interview question? Palindromic Substrings

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

Given a string s, our task is to return the number of palindromic substrings in it. A string is considered a palindrome if 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".

Using Efficient Approach (Expand Around Center)

The “Expand Around Center” approach is an efficient method to count palindromic substrings. The idea is to consider every possible center of a palindrome and expand outwards as long as the substring remains a palindrome. This can be done for both odd-length and even-length palindromes.

def countSubstrings(self, s: str) -> int:
    res = 0
    for i in range(len(s)):
        res += self.countPali(s, i, i)
        res += self.countPali(s, i, i + 1)

    return res

def countPali(self, s: str, l: int, r: int):
    res = 0
    while l >= 0 and r < len(s) and s[l] == s[r]:
        res += 1
        l -= 1
        r += 1

    return res

Explanation

1. Outer Loop: Iterates through each character in the string.

   • For each character, the countPali method is called twice.
     • First call treats the character itself as the center (for odd-length palindromes).
     • Second call treats the space between the character and the next one as the center (for even-length palindromes).

2. countPali Method: Expands outward from the given center (l, r) and counts palindromes.

   • While expanding, it checks if characters on both sides are the same.
   • If they are, it increments the count res and continues to expand outward.
   • Stops when characters do not match or when boundaries of the string are reached.

Time Complexity: O(n^2) - The outer loop runs n times, and for each iteration, the inner while loop can also run n times in the worst case.

Space Complexity: O(1) - We use a constant amount of extra space.

Using Efficient Approach 2 (Two Pointers with Zip)

Another method involves using two pointers in conjunction with Python’s zip function to compare characters from opposite ends of potential palindromic substrings.

def countSubstrings(self, s: str) -> int:
    count = 0
    for i in range(len(s)):
        count += 1
        for a, b in zip(reversed(s[:i]), s[(i + 1):]):
            if a == b:
                count += 1
            else:
                break
        for a, b in zip(reversed(s[:(i + 1)]), s[(i + 1):]):
            if a == b:
                count += 1
            else:
                break
    return count

Explanation

1. Outer Loop: Iterates through each character in the string.
2. For each character, the count is incremented because a single character is always a palindrome.
3. Two nested loops are used:
   • The first loop compares characters in reversed substring before the current index with characters after the current index.
   • The second loop compares characters in reversed substring up to the current index with characters after the current index.
4. These comparisons continue as long as characters match. If a mismatch is found, the loop breaks.

Time Complexity: O(n^2) - Similar to the first approach, the outer loop runs n times, and each nested loop can run n times in the worst case.

Space Complexity: O(1) - Uses a constant amount of extra space.

Conclusion

In this article, we explored how to count palindromic substrings in a given string. We discussed an efficient approach using the expand around center method and another using two pointers with the zip function. Both approaches effectively solve the problem within a time complexity of O(n^2).

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 70 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Number of Longest Increasing Subsequence"