C++ Bottom Up DP soln with explanation

  • 0
    class Solution {
        int countSubstrings(string s) {
            // cache to store start index of first char of the palindrome
            // value as list of all end indeices of palindromes
            unordered_map<int,vector<int>> dp;
            int result = 0;
                return result;
            //base case for the last char
            dp[s.size()-1] = vector<int>{s.size()-1};
            ++result;// single character itself is palindrome
            for(int left = s.size()-2;left>=0;--left){
                dp[left] = vector<int>{left};
                ++result; // single character itself is palindrome
                for(int end:dp[left+1]){
                    if((end == left + 1) && s[end] == s[left]){ // check if this and next char are same
                    if(end+1 < s.size() && s[end+1] == s[left]){
            return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.