Palindromic Substrings
Medium
String
Dynamic Programming
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
Example 2
Input: s = "aaa"
Output: 6

Constraints

  • •1 <= s.length <= 1000
  • •s consists of lowercase English letters.
Time Complexity
O(n²)
Space Complexity
O(1)
14
Case 1
Input: "abc"
Expected: 3
Case 2
Input: "aaa"
Expected: 6
Case 3
Input: "aba"
Expected: 4