Java DP solution O(MN)
\nDefine:  dp[i][j][k] is the number of substrings where s[0,..i] and t[0, j] have k different characters.\n\nCase 1: same character s[i] == t[j]\n dp[i][j][0] 
\nDefine:  ```dp[i][j][k]``` is the number of substrings where ```s[0,..i]``` and ```t[0, j]``` have ```k``` different characters.\n\nCase 1: same character ```s[i] == t[j]```\n* ```dp[i][j][0] = dp[i-1][j-1][0]```, which means the number of same substrings of ```s[0,...,i]``` and ```t[0,...,j]``` equals to those of  ```s[0,...,i-1]``` and ```t[0,...,j-1]```.\n* ```dp[i][j][0] = dp[i-1][j-1][0]```, which means the number of one-character-diff substrings of ```s[0,...,i]``` and ```t[0,...,j]``` equals to those of  ```s[0,...,i-1]``` and ```t[0,...,j-1]```.\n\t\nCase 2: different characters ```s[i] != t[j]```\n* ```dp[i][j][0] = 0```, which means ```s[0,...,i]``` and ```t[0,...,j]``` are different.\n* ```dp[i][j][1] = dp[i-1][j-1][0]```, which means ```s[0,...,i-1]``` and ```t[0,...,j-1]``` have ```dp[i-1][j-1][0]``` same substrings but the character ```s[i]``` and ```t[j]``` are different.\n\nThe answer is the total number of substrings that differ by one character. So, sum up all the ```dp[i][j][1]```.\n\n\n```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int n = s.length(), m = t.length(), ans = 0;\n        int[][][] dp = new int[n+1][m+1][2];\n        for(int i = 0; i < n; i++) {\n            for(int j = 0; j < m; j++) {\n                if(s.charAt(i) == t.charAt(j)) {\n                    dp[i+1][j+1][0] = dp[i][j][0] + 1;\n                    dp[i+1][j+1][1] = dp[i][j][1];\n                }\n                else {\n                    dp[i+1][j+1][1] = dp[i][j][0] + 1;\n                }\n                ans += dp[i+1][j+1][1];\n            }\n        }\n        return ans;\n    }\n}\n```
[]