Dynamic programming O(n^2)
We can do it in O(n^2) complexity by following way:\n\ndp[i][j]]: keep track of  number of substring for s and t that ends at position i and j respectively such
We can do it in O(n^2) complexity by following way:\n\n**dp[i][j]]**: keep track of  number of substring for s and t that ends at position i and j respectively such that they are exactly equal.\n**dp2[i][j]]**: keep track of  number of substring for s and t that ends at position i and j respectively such that they differ by one character.\n\nthen transitions are as follows:\nif they character at i and j are equal then:\ndp[i][j]= dp[i-1][j-1] \ndp2[i][jj]= dp2[i-1][j-1]+1\notherwise \ndp[i][j]= dp[i-1][j-1]+1\ndp2[i][j]=0 \n The answer is summation of all value of dp[i][j]\n```\nclass Solution {\npublic:\n      #define ll int\n    ll dp[101][101]; \n    ll dp2[101][101]; \n    int countSubstrings(string s, string t) {\n        \n        \n        ll ans=0 ;\n        for(ll i=0;i<s.size();i++)\n        {\n            for(ll j =0;j<s.size();j++)\n            {\n                dp[i][j]=0;\n                dp2[i][j]=0;\n            }\n        }\n        for(ll i=0;i<s.size();i++)\n        {\n            for(ll j =0;j<t.size();j++)\n            {\n                \n              if(s[i]==t[j])\n              {\n                  ll x=i-1>=0 && j-1>=0 ? dp[i-1][j-1]:0;\n                   ll y= i-1>=0 && j-1>=0?dp2[i-1][j-1]:0;\n                  dp[i][j]=x;\n                  dp2[i][j]=y+1; \n              }\n                else\n                {\n                    ll x= i-1>=0 && j-1>=0?dp2[i-1][j-1]:0;\n                    dp[i][j]=x+1;\n                    dp2[i][j]=0; \n                }\n                ans+=dp[i][j];\n            }\n        }\n        \n        return ans; \n    }\n};\n```
[]