Java | DP explained
\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        /*\n            diff0[i][j] = number of s substring ending at i is t substring
```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        /*\n            diff0[i][j] = number of s substring ending at i is t substring ending at j\n            diff1[i][j] = number of s substring ending at i is 1-char diff from substring of t ending at j\n            if (s.charAt(i) == t.charat(j)){\n                diff0[i][j] = diff0[i-1][j-1]+1;\n                diff1[i][j] = diff1[i-1][j-1];\n            } else {\n                diff0[i][j] = 0;\n                diff1[i][j] = diff0[i-1][j-1]+1;\n            }\n        */\n        int count = 0, lenS = s.length(), lenT = t.length();\n        int[][] diff0 = new int[lenS][lenT];\n        int[][] diff1 = new int[lenS][lenT];\n        for (var i=0; i<lenS; i++){\n            for (var j=0; j<lenT; j++){\n                var match = s.charAt(i) == t.charAt(j);\n                if (i==0 || j==0){\n                    diff0[i][j] = match ? 1 : 0;\n                    diff1[i][j] = match ? 0 : 1;\n                } else {\n                    if (match){\n                        diff0[i][j] = diff0[i-1][j-1]+1;\n                        diff1[i][j] = diff1[i-1][j-1];\n                    } else {\n                        diff0[i][j] = 0;\n                        diff1[i][j] = diff0[i-1][j-1] + 1;\n                    }\n                }\n                \n                count += diff1[i][j];\n            }\n        }\n        return count;\n    }\n}\n```
[]