Dynamic Programming Detailed Thought process
Think of all the possible scenarios:\nI will consider state as (i,j)\nMy state here is I am going to lookout for all the substrings differing by one character a
Think of all the possible scenarios:\nI will consider state as (i,j)\nMy state here is I am going to lookout for all the substrings differing by one character and ending at \'i\' and \'j\'\n\nSo, if (s[i-1] == t[i-1])\n         state(i,j) = state(i-1,j-1)\n\t   else\n\t     state(i,j) = 1 + [all same substrs ending in (i-1) and (j-1)]\n\t\t \nTo get all the equal substrs, we apply another simple dp.\n\nMy answer is summation of all states(i,j)\n\n```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int len1 = s.length();\n        int len2 = t.length();\n        vector<vector<int>> sameStr(len1+1,vector<int>(len2+1, 0));\n        \n        for(int i = 1; i <= len1; i++){\n            for(int j = 1; j <= len2; j++){\n                if(s[i-1] == t[j-1]){\n                    sameStr[i][j] = 1 + sameStr[i-1][j-1];\n                }\n            }\n        }\n        \n        vector<vector<int>>diffStr(len1+1,vector<int>(len2+1,0));\n        int cnt = 0;\n        for(int i = 1; i <= len1; i++){\n            for(int j = 1; j <= len2; j++){\n                if(s[i-1] != t[j-1]){\n                    diffStr[i][j] = 1 + sameStr[i-1][j-1]; \n                } else {\n                    diffStr[i][j] = diffStr[i-1][j-1];\n                }\n                cnt += diffStr[i][j];\n            }\n        }\n        return cnt;\n    }\n};\n```
['Dynamic Programming']