Problem Statement:
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 strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Constraints
1 <= s.length <= 1000sconsists of lowercase English letters.
Approach:
- A 2D DP table
dp[i][j]is used, wheredp[i][j] = trueif substring s[i..j] is a palindrome. - All single characters
(s[i])are palindromes →mark dp[i][i] = true. - Check substrings of length 2 → if two consecutive characters are equal, mark them as palindromes.
- For substrings of
length ≥ 3 → a substring s[i..j]is palindrome if- The first and last characters match
(s[i] == s[j]). - The inner substring
s[i+1..j-1]is palindrome(dp[i+1][j-1] = true).
- The first and last characters match
- Count all palindromic substrings while filling the table.
- Return the
total count of palindromic substrings.
Time & Space Complexity:
Time Complexity: O(n2)
Space Complexity: O(n2)
Dry Run
Input: s = "aaa"
Step 0: Start Function countSubstrings("aaa")
n = 3
dp = 3x3 matrix filled with null
ans = 0
First loop (single characters):
i = 0 → dp[0][0] = true → ans = 1
i = 1 → dp[1][1] = true → ans = 2
i = 2 → dp[2][2] = true → ans = 3
Also check for 2-length palindromes:
i = 0 → s[0] == s[1] → "aa" → dp[0][1] = true → ans = 4
i = 1 → s[1] == s[2] → "aa" → dp[1][2] = true → ans = 5
Now:
dp =
[
[T, T, null],
[ , T, T ],
[ , , T ]
]
Second loop (length >= 3):
len = 3:
i = 0, j = 2
- s[0] == s[2] ? "a" == "a" ✔
- dp[1][1] == true ✔
- So dp[0][2] = true, ans = 6
Loop ends
Step 3: End
Return ans = 6
Output: 6
Visualisation:
var countSubstrings = function(s) {
let n = s.length;
let dp = Array.from({ length: n }, () => Array(n).fill(null));
let ans = 0;
for (let i = 0; i < n; i++) {
dp[i][i] = true;
++ans;
if (i < n - 1 && s[i] === s[i + 1]) {
dp[i][i + 1] = true;
++ans;
}
}
for (let len = 3; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
let j = i + len - 1;
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
++ans;
}
}
}
return ans;
};
def countSubstrings(s):
n = len(s)
dp = [[None] * n for _ in range(n)]
ans = 0
for i in range(n):
dp[i][i] = True
ans += 1
if i < n - 1 and s[i] == s[i + 1]:
dp[i][i + 1] = True
ans += 1
for length in range(3, n + 1):
for i in range(0, n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
ans += 1
return ans
public class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
++ans;
if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
++ans;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
++ans;
}
}
}
return ans;
}
}
#include <vector>
#include <string>
int countSubstrings(const std::string &s) {
int n = (int)s.length();
std::vector> dp(n, std::vector(n, false));
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
++ans;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = true;
++ans;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
++ans;
}
}
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int countSubstrings(const char *s) {
int n = strlen(s);
if (n == 0) return 0;
char **dp = (char **)malloc(n * sizeof(char *));
for (int i = 0; i < n; i++) {
dp[i] = (char *)calloc(n, sizeof(char));
}
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
++ans;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
++ans;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = 1;
++ans;
}
}
}
for (int i = 0; i < n; i++) free(dp[i]);
free(dp);
return ans;
}
using System;
public class Solution {
public static int CountSubstrings(string s) {
int n = s.Length;
bool[,] dp = new bool[n, n];
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i, i] = true;
++ans;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i, i + 1] = true;
++ans;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1, j - 1]) {
dp[i, j] = true;
++ans;
}
}
}
return ans;
}
}
