palindromic-substrings.ts

/**
 * 647. Palindromic Substrings  (Medium)
 * Link: https://leetcode.com/problems/palindromic-substrings/
 *
 * Return the number of palindromic substrings in `s`. Substrings at different
 * positions count separately even if identical.
 *
 * Example:
 *   Input:  s = "aaa"
 *   Output: 6            // "a","a","a","aa","aa","aaa"
 *
 * Approach:
 *   Expand around center. For each of the 2n-1 centers (odd and even), expand
 *   outward while the characters match, counting one palindrome per successful
 *   expansion. Summing over all centers gives the total.
 *
 * Time:  O(n^2)
 * Space: O(1)
 */
export function countSubstrings(s: string): number {
  let count = 0;

  const expand = (left: number, right: number): void => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i); // odd-length
    expand(i, i + 1); // even-length
  }

  return count;
}