# Leetcode 647. Palindromic Substrings

[link](https://leetcode.com/problems/palindromic-substrings)

---

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.

---

The code defines a helper function called helper. This function takes four arguments: l (left index), r (right index), s (the input string), and res (the current count of palindromic substrings). It uses a while loop to expand the palindrome from the center, comparing characters at s[l] and s[r]. Whenever a palindrome is found, it increments the res variable and continues expanding. It keeps expanding the palindrome until characters at s[l] and s[r] are not equal, or until the indices go out of bounds. Then, it returns the updated res.

The main loop of the function iterates over each character in the input string s using the variable i.

Inside the loop, it calls the helper function twice:

First, it calls helper(i, i, s, res). This means it checks for palindromes with an odd length, where i is the center of the palindrome. It updates the res variable whenever a palindrome is found.

Second, it calls helper(i, i + 1, s, res). This means it checks for palindromes with an even length, where i and i + 1 are the centers of the palindrome. Again, it updates the res variable whenever a palindrome is found.
Finally, the function returns the count of palindromic substrings found, stored in the res variable.

#### Solution 1

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0

        def helper(l, r, s, res):
            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)):
            l, r = i, i
            res = helper(l, r, s, res)

        for i in range(len(s)):
            l, r = i, i + 1
            res = helper(l, r, s, res)

        return res
            

O(T): O(n^2)
O(S): O(1)