Skip to content

647. Palindromic Substrings

Two Pointers String Dynamic Programming

Problem - Palindromic Substrings

Medium

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.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countSubstrings(self, s: str) -> int:
        result, n = 0, len(s)
        for k in range(n * 2 - 1):
            i, j = k // 2, (k + 1) // 2
            while ~i and j < n and s[i] == s[j]:
                result += 1
                i, j = i - 1, j + 1

        return result

Submission Stats:

  • Runtime: 115 ms (82.69%)
  • Memory: 17.8 MB (50.34%)