Palindromic Substrings

medium string dp

Problem

Given a string s, return the number of palindromic substrings in it. Substrings at different positions are counted separately even if they look the same.

Every palindrome has a center: either a single character (odd length) or the gap between two characters (even length). Sweep every center and expand outward while the two ends match; each successful expansion contributes one more palindrome.

Inputs = "aaa"

Output6

"a", "a", "a", "aa", "aa", "aaa".

def count_substrings(s):
    n = len(s)
    count = 0
    for i in range(n):
        count += expand(s, i, i)
        count += expand(s, i, i + 1)
    return count

def expand(s, l, r):
    c = 0
    while l >= 0 and r < len(s) and s[l] == s[r]:
        c += 1
        l -= 1
        r += 1
    return c

function countSubstrings(s) {
  let count = 0;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; }
  };
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return count;
}

class Solution {
    int count = 0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return count;
    }
    void expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++; l--; r++;
        }
    }
}

int countSubstrings(string s) {
    int count = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { count++; l--; r++; }
    };
    for (int i = 0; i < (int)s.size(); i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return count;
}

Explanation

Every palindrome has a center it is symmetric around. The clever trick here is to stand at each possible center and expand outward, counting palindromes as we go, instead of checking every substring from scratch.

There are two kinds of center. An odd-length palindrome is centered on a single character, so we start with l = r = i. An even-length one sits in the gap between two characters, so we start with l = i and r = i + 1.

The expand helper grows the window while the ends stay in bounds and match (s[l] == s[r]). Each time they match, that whole window is a palindrome, so we add one to count, then step l left and r right to check the next bigger window.

Example: s = "aaa". The odd center at index 0 gives "a"; at index 1 it gives "a" then expands to "aaa"; the even centers catch the two "aa" pairs. Adding everything up gives 6.

Since each of the roughly 2n centers can expand at most n times, the work is quadratic but uses only a couple of counters for memory.

Time: O(n²) Space: O(1)