Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Medium

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.

Examples

Input:s = "abc"
Output:3
Three palindromic strings: "a", "b", "c".
Input:s = "aaa"
Output:6
Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Expand Around Center

Approach

Similar to finding the Longest Palindromic Substring, we can iterate through the string and treat each character (and each pair of characters) as the center of a potential palindrome. We expand outwards to the left and right. Every time the characters match, it means we found a new valid palindrome, so we increment our count. We do this for both odd-length and even-length palindromes at every index.

Complexity Analysis

Time Complexity
O(n^2)
Space Complexity
O(1)

Expanding around a center takes O(n) time, and we check 2n-1 possible centers. Thus, time complexity is O(n^2). Space complexity is O(1) as we just keep a counter.

Solution.java
class Solution {    public int countSubstrings(String s) {        if (s == null || s.length() == 0) return 0;                int count = 0;                for (int i = 0; i < s.length(); i++) {            // Count odd length palindromes centered at i            count += expandAroundCenter(s, i, i);                        // Count even length palindromes centered between i and i+1            count += expandAroundCenter(s, i, i + 1);        }                return count;    }        private int expandAroundCenter(String s, int left, int right) {        int count = 0;        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {            count++;            left--;            right++;        }        return count;    }}