C++ Code | Brute Force and DP both approaches
\n//BRUTE FORCE\n\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans = 0;  // for holding answer\n        int len1 = s.l
```\n//BRUTE FORCE\n\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans = 0;  // for holding answer\n        int len1 = s.length(), len2 = t.length(); // compute length of both strings "s" and "t"\n        for(int i = 1; i <= len1; i++)  // length of both substrings of s and t\n        {\n            for(int j = 0; j+i <= len1; j++)  // find subtring of s of length i\n            {\n                string s1 = s.substr(j, i);  // s1 -> subtring of s of length i\n                for(int k = 0; k+i <= len2; k++)  // subtring of t of length i\n                {\n                    string t1 = t.substr(k, i); // t1 -> subtring of t of length i\n                    int f = 1;\n                    for(int p = 0; p < i; p++)  // compare the characters of both s1 and t1 substrings \n                    {\n                        if(s1[p] != t1[p])\n                            f--;\n                    }\n                    if(f == 0) ans++;  // if they differ by only one character, then add the count\n                }\n            }\n        }\n        return ans;  // return final answer\n    }\n};\n\n\n// DP Approach\n\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans = 0;\n        int len1 = s.length(), len2 = t.length();\n        vector<vector<int>> same(len1+1, vector<int>(len2+1, 0));  // if s[i-1] == t[j-1]\n        auto differ = same;  // if s[i-1] != t[j-1]\n        for(int i = 1; i <= len1; i++)\n        {\n            for(int j = 1; j <= len2; j++)\n            {\n                if(s[i-1] == t[j-1])  \n                {\n                    same[i][j] = 1 + same[i-1][j-1];  // if it is same then just add 1 more to the count of substrings having equal characters\n                    differ[i][j] = differ[i-1][j-1]; // number of differing substrings by one character will remain same\n                }\n                else  \n                    differ[i][j] = same[i-1][j-1] + 1;  // add 1 to the substrings having same character upto i-1 of string s and j-1 of string t\n                ans += differ[i][j];  // add the differing substrings count to final answer\n            }\n        }\n        return ans;  // return final answer\n    }\n};\n```
['String', 'Dynamic Programming', 'C++']