LeetCode #647: Palindromic Substrings

LeetCode Solutions

https://leetcode.com/problems/palindromic-substrings/

To solve this problem, we can use the expanding around center approach. We consider each character in the string as the center of the palindrome and try to expand to both sides to check if it is a palindrome. There are two types of palindromes: even length (like “aa”) and odd length (like “aba”). So, for each center, we check both types of palindromes.

For each center, we keep expanding outwards until we reach the end of the string or a non-matching character is found. For every palindrome we find, we increase the count.

Algorithm Steps:

  1. Initialize a variable res to 0.
  2. Define a function isPali that will take two arguments, the left and right indices, and will return the count of palindromic substrings that can be formed around these indices.
  3. Loop through the string s and for each character i, call the isPali function twice: first for odd length palindromes by passing i twice, and then for even length palindromes by passing i and i+1.
  4. Add the count of palindromic substrings returned by the isPali function to the res variable.
  5. Return the res variable

Here is the solution in python3:

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

        for i in range(len(s)):
            res += isPali(i, i)
            res += isPali(i, i+1)
        return res

Time Complexity

The time complexity of this solution is O(n^2), where n is the length of the input string. This is because we are looping through the string twice (once to consider odd length palindromes and once to consider even length palindromes), and for each character, we might have to expand to the left and right to check if it forms a palindrome. The worst case would be a string of length n that contains all identical characters.

Space Complexity

The space complexity of this solution is O(1), as we are only using constant space to keep track of variables.