Java Dynamic Programming Time O(nm) Space O(nm)
Example: s="abbab", t="bbbbb"\nCompare each substring of s {a,ab,abb,abba,abbab} with each substring of \nt {b,bb,bbb,bbbb,bbbb}\n\nUsing dp, there are only two
Example: s="abbab", t="bbbbb"\nCompare each substring of s {a,ab,abb,abba,abbab} with each substring of \nt {b,bb,bbb,bbbb,bbbb}\n\nUsing dp, there are only two cases, when s[i]==t[j] or s[i]!=t[j]\nfor example:\n\n(1) when compare s="abb" with t="bbb", since s[2]==t[2], you only need to know what is the preivous result, that is when compare s="ab" with t="bb"\n\n(2) when compare s="abba" with t="bbbb", since s[3]!=t[3], you need to know how many consecutive characters before s[3] and before t[3] are the same, here two characters "bb" in "abba" are the same with "bb" in "bbbb", so the result of compaing s=abba and t=bbbb is 1+number of consecutively same characters, becuase you will have {bbb,bb,b} differs in 1 character with {bba,ba,a} correspodingly\n\ndp1 used for saving the number of previous consecutive same characters\ndp2 is the result of comparing s[ 0 to i ] with t[ 0 to j ]\n\n```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int len1=s.length();\n        int len2=t.length();\n        int res=0;\n        int[][] dp1=new int[len1][len2];\n        int[][] dp2=new int[len1][len2];\n        \n        for(int i=0;i<len1;i++){\n            char c1=s.charAt(i);\n            for(int j=0;j<len2;j++){\n                char c2=t.charAt(j);\n                if(c1==c2){\n                    if(i==0||j==0){\n                        dp1[i][j]=1;\n                    }\n                    else{\n                        dp1[i][j]=dp1[i-1][j-1]+1;\n                        dp2[i][j]=dp2[i-1][j-1];\n                    }\n                }\n                else{\n                    dp1[i][j]=0;  \n                    if(i==0||j==0){\n                        dp2[i][j]=1;\n                    }\n                    else{\n                        dp2[i][j]=dp1[i-1][j-1]+1;\n                    }\n                }\n                res+=dp2[i][j];\n            }\n        }\n        return res;   \n    }\n}\n```
[]