Given a string s, return the number of palindromic substrings in it.

Example 1:

• Input: s = "abc"
• Output: 3
• Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2:

• Input: s = "aaa"
• Output: 6

Constraints:

• 1 <= s.length <= 1000

Expand around center and count every valid expansion.

Expand Around Center Counting

graph TD
    Problem["Problem of Size N"] --> Sub["Break into Subproblems DP[i]"]
    Sub --> Base["Base Cases: DP[0], DP[1]"]
    Base --> Trans["State Transition: DP[i] = f(DP[i-1], DP[i-2], ...)"]
    Trans --> Table["Fill DP Table / Variables"]
    Table --> Result["Return DP[N]"]

function countSubstrings(s) {
  let count = 0;
  function 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;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)
• Explanation: Center expansion counting.

function countSubstrings(s) {
  let count = 0;
  function 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;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)
• Explanation: O(n^2) time center expansion.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Increment total count every time s[l] === s[r] during outwards expansion.

1. Count expansions from single and double centers.

👉 Solve this problem interactively in the DSA Lab