647. Palindromic Substrings

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: s = "abc" Output: 3

Input: s = "aaa" Output: 6

Solution Approach

The solution involves expanding around each possible center in the string to count all palindromic substrings by checking for valid palindromes from the center outwards.

Algorithm

1. Center Expansion: Iterate through each possible center of the palindrome, which can be a single character or the space between two characters, and expand outwards to check for palindromic substrings.
2. Two Pointers: For each center, use two pointers (l and r) to expand to the left and right, respectively, while the characters at these pointers are equal, counting each valid palindrome found.
3. Count Palindromes: Each time a palindrome is identified during expansion, increment the result counter. Continue until all possible centers have been explored.

Implement

    class Solution:
  def countSubstrings(self, s: str) -> int:
      #notice the return question 
      res = 0
      n = len(s)
      # 0 1 2 3 4   n = 5. mid = 0 ~ 8  left 0 ~ 4 right = 0 ~ 4
      for mid in range(n * 2 - 1):
          l = mid // 2
          r = l + mid % 2
          while l >= 0 and r < n and s[l] == s[r]:
              res += 1
              l -= 1
              r += 1
      return res
        

    
    

Twitter  facebook  Email