BinarySearch 0321 Trimmed Palindromes

Problem statement

https://binarysearch.com/problems/Trimmed-Palindromes/

Solution

It is equal to Leetcode 0647. Palindromic Substrings.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        def helper(i, j):
            while i >= 0 and j < len(s) and s[i] == s[j]:
                i, j = i - 1, j + 1
            return (j-i)//2
        
        return sum(helper(k,k) + helper(k,k+1) for k in range(len(s)))