647. Palindromic Substrings

📝 Problem Details

• Title: 647. Palindromic Substrings
• Link: https://leetcode.com/problems/palindromic-substrings/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input string s return the number of palindromic substrings in it

💭What Were My Initial Thoughts?

- enumeration question, except instead of return all different types of palindromic substrings we are only needed to return the number of ways
- backtracking since we need to construct all possible palindromic substrings
- identifiable subproblem which suggests DFS backtracking with memoization 
	- any longer palindrome is bult upon a shorter palindrome
	- we can use dfs to recursively construct palindromic substrings
	- memoization can assist in avoiding recomputing the same substrings

💡 Explanation of Solution

- start from index i and try to form palindromes ending at j
- if s[i:j] is a palindrome, recursively explore further
- memoize results to pervent redundant computations

⌛ Complexity Analysis

class Solution {
public:
    vector<vector<int>> memo;  // Memoization table to store previously computed results
 
    // Helper function to check if a substring s[i:j] is a palindrome
    bool isPalindrome(string &s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) return false;  // If characters mismatch, it's not a palindrome
            i++, j--;  // Expand towards the center
        }
        return true;
    }
 
    // Recursive DFS function to count palindromic substrings in s[i:j]
    int dfs(string &s, int i, int j) {
        if (i > j) return 0;  // Base case: Invalid substring (out of bounds)
        
        if (memo[i][j] != -1) return memo[i][j];  // Return previously computed result if available
 
        int count = 0;
 
        // Check if s[i:j] is a palindrome
        if (isPalindrome(s, i, j)) count++;
 
        // Recursively count substrings by:
        // - Including the left character
        // - Including the right character
        // - Avoiding double-counting the overlapping middle part
        count += dfs(s, i + 1, j) + dfs(s, i, j - 1) - dfs(s, i + 1, j - 1);
 
        return memo[i][j] = count;  // Store the computed result in the memo table
    }
 
    // Main function to count palindromic substrings
    int countSubstrings(string s) {
        int n = s.size();
        memo.assign(n, vector<int>(n, -1));  // Initialize memoization table with -1 (uncomputed)
        return dfs(s, 0, n - 1);  // Start DFS from the full string
    }
};

💻 Implementation of Solution