Java DP solution with detail explanation. O(nm) runtime.
Intuition\n1. Let\'s first look at the case where s and t differ by 1 letter and all the other letters are the same. For example, if we have something like "com
# Intuition\n1. Let\'s first look at the case where s and t differ by 1 letter and all the other letters are the same. For example, if we have something like "com" and "coe" -> there\'s 3 pairs {com, coe}, {om, oe}, {m,e}. From this, we can see that total # of different pairs formed becase of "m" and "e" being different is longest common substring before m and e plus 1 for the pair {m,e}. Hence it would be LCS being "co" which is lenght 2 + 1. \n\nWe can say that m and e from the example above is at position i and j. We can denote this as if s(i) != t(j) then diff[i][j] == LSC(i - 1, j - 1) + 1.\n\n2. Let\'s look at when s(i) == t(j), then we know that including letter at s(i) and t(j) itself does not cause any more pairs at this point in time. For example, let\'s image building the string "com" and "coe". At s(i)==s(j) = o, adding o to c doesn\'t cause any additional pairs. Hence the number of differing by 1 pairs at s(i) and t(j) is the same as before. \n\nLet\'s denote that as s(i) == t(j), then diff[i][j] == diff[i - 1][j - 1]. \n\nThis will help us count cases where the differ letter is in the beging i.e. {tom, com}, since for o and m we will be counting them as a difference of 1 due to {t,c} being different. \n\n3. Edge cases (length 1 substring) -> when we count substrings that are lenght 1 and differ by 1. For example in 2 even if s(i)==s(j) the letters s(i) and s(j) can still cause a new pair being the length 1 substring pair. i.e. {o, c} {o, e} etc. We count the length 1 pairs by looking at when i == 0 and j == 0 which will allow us to build lenght 1 substrings from s and t. \n\nHence, if i == 0 or j == 0, diff[i][j] = 1 if s(i) == t(j) else = 0. \n\n4. Answer is simple the sum of all the differences at each i, j. \n\n# Approach\n\nUse two nested arays to loop through s and t for each index i and j. Use two 2d arrays to keep track of diff[i][j] and lcs[i][j]. Sum up all the values in diff array. \n\nI would recommend drawing out a few LCS and diff matrix to understand this logic better if there is any confusion.\n\n# Complexity\n- Time complexity:\nFor s and t lenght of n and m respectively runtime is O(n*m) since we just loop once (nested) for each i and j being index of string s and t. \n\n- Space complexity:\nSince I used 2 2d arrays of nxm it\'s O(2n*m). We can reduce to O(n) or O(m) this by using 1 d arrays and just keeping track of the previous row. \n\n# Code\n```\nclass Solution {\n    public int countSubstrings(String s, String t) {\n        int n = s.length();\n        int m = t.length(); \n        \n        int [][] lcs = new int[n][m];\n        int [][] diff = new int[n][m]; // we will return the sum of all the cells as the answer\n        int count = 0; \n        for (int i = 0; i < n; i++) { // loop for string s \n            for (int j = 0; j < m; j++) { // loop for string t \n                if (s.charAt(i) == t.charAt(j)) {\n                    // diff same as difference before we added this letter since it doesn\'t do \n                    // anything \n                    diff[i][j] = (i == 0 || j == 0) ? 0 : diff[i - 1][j - 1]; \n                    // add 1 to the lcs we\'ve seen at this point since s(i) == t(j)\n                    lcs[i][j] = (i == 0 || j == 0) ? 1 : lcs[i - 1][j - 1] + 1; \n                } else {\n                    diff[i][j] = (i == 0 || j == 0) ? 1 : lcs[i - 1][j - 1] + 1;\n                    lcs[i][j] = 0; \n                }\n                count += diff[i][j];\n            }\n        }\n\n        return count;\n    }\n}\n```
['Java']