# [Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)
###### tags: `Leetcode`, `Medium`, `Dynamic Programming`

## Approach

* We need to consider odd and even length substrings
* The basic idea is to consider each index position of the substring as the middle and span outwards while checking for palindrome. Every time we find a palindrome we increment the result by one
* **For odd length substrings:**
* Initial L and R pointer will be the same as the index position of our `for` loop
* Since L and R are the same at the beginning, increment result by one
* Move L one place to the left and move R one place to the right (within the bounds of the string's length) and repeat the check
* **For even length substrings:**
* Initial L will point to the index position of our `for` loop and R will point to `L + 1`
* Check if `s[L] == s[R]` and if true increment result by one.
* Move L one place to the left and move R one place to the right (within the bounds of the string's length) and repeat the check
* Return the result

## Asymptotic Analysis
### Time Complexity: **O(N²)**
### Space Complexity: **O(1)**

## Code

class PalindromicSubstring:
    def count_substrings(self, s: str) -> int:
        result = 0
        for index in range(len(s)):
            # For odd length substrings
            left = right = index
            while left >= 0 and right < len(s) and s[left] == s[right]:
                result += 1
                left -= 1
                right += 1

            # For even length substrings
            left = index
            right = left + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                result += 1
                left -= 1
                right += 1
        return result


input_string = 'aaab'
ps = PalindromicSubstring()
print(f"Number of palindromic substring in the string '{input_string}' = {ps.count_substrings(input_string)}")