Palindromic Substrings medium

Problem Statement

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

A substring is a contiguous sequence of characters within a 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".

Steps and Explanation

The core idea is to use a dynamic programming approach. We create a boolean table dp where dp[i][j] is true if the substring from index i to j (inclusive) is a palindrome, and false otherwise. We iterate through all possible substring lengths, checking if they are palindromes.

1. Initialization: Single characters are always palindromes, so we initialize the diagonal of the dp table to true.
2. Iteration: We iterate through substrings of increasing length. For each substring s[i...j]:
   • If s[i] == s[j] and (the substring s[i+1...j-1] is a palindrome – which we already know from the previous iterations), then s[i...j] is also a palindrome. We set dp[i][j] = true.
3. Counting Palindromes: As we fill the dp table, we count the number of true values, which represents the total number of palindromic substrings.

Code (C++)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int countSubstrings(string s) {
    int n = s.length();
    if (n == 0) return 0;

    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;

    // Single characters are palindromes
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        count++;
    }

    // Check for palindromes of length 2 and greater
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || dp[i + 1][j - 1]) { //len==2 handles substrings of length 2
                    dp[i][j] = true;
                    count++;
                }
            }
        }
    }

    return count;
}

int main() {
    string s1 = "abc";
    string s2 = "aaa";
    cout << "Number of palindromic substrings in \"" << s1 << "\": " << countSubstrings(s1) << endl; // Output: 3
    cout << "Number of palindromic substrings in \"" << s2 << "\": " << countSubstrings(s2) << endl; // Output: 6
    return 0;
}

Complexity Analysis

• Time Complexity: O(n^2), where n is the length of the string. This is because we iterate through all possible substrings, which takes quadratic time.
• Space Complexity: O(n^2), due to the dp table used for dynamic programming. We could potentially optimize space by using only one row of the DP table, but it doesn't significantly change the overall complexity.