[LeetCode] 647. Palindromic Substrings

Table of Contents

Description

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 substrings: “a”, “b”, “c”.

Example 2:

Input: s = "aaa";
Output: 6
Explanation: Six palindromic substrings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Approach

This problem uses an approach similar to LeetCode 5. Longest Palindromic Substring, applying the expand-around-center (two pointer) technique. By treating each character and the gap between every pair of characters as potential centers, we expand outward to count all palindromic substrings. The main difference is that here we count every palindrome, while LeetCode 5 focuses on finding the longest one.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  let result = 0;

  // Iterate over each character in the string as the center of palindrome
  for (let i = 0; i < s.length; i++) {
    // Get all odd length palindromic substrings centered at i
    const oddPalindromicStrings = getPalindromicStrings(s, i, i);
    // Get all even length palindromic substrings centered between i and i+1
    const evenPalindromicStrings = getPalindromicStrings(s, i, i + 1);

    // Add the count of found palindromic substrings to the result
    result += oddPalindromicStrings.length + evenPalindromicStrings.length;
  }

  return result;
};

function getPalindromicStrings(s, start, end) {
  const palindromicStrings = [];

  // Expand outwards while characters at start and end are equal
  for (; start >= 0 && end < s.length; start--, end++) {
    if (s[start] !== s[end]) break; // Break if characters don't match

    // Add the palindrome substring to the array
    palindromicStrings.push(s.slice(start, end + 1));
  }

  return palindromicStrings;
}

Complexity Analysis

Time Complexity

The time complexity is $O(n^2)$, where $n$ is the length of the string. For each possible center, we may expand up to $n$ times to check for palindromic substrings.

Space Complexity

The space complexity is $O(n^2)$ if all palindromic substrings are stored. If only the count is maintained and no substrings are stored, the space complexity would be $O(1)$.