Java O(n^2) - beats 100%
diff[i][j] here is the number of substrings differing in 1 character ending in indices i and j in strings s and t respectively\n\nid[i][j] is the number of iden
`diff[i][j] ` here is the number of substrings differing in 1 character ending in indices `i` and `j` in strings `s` and `t` respectively\n\n`id[i][j]` is the number of identical substrings ending in indices `i` and `j` in strings `s` and `t` respectively\n\nThe answer is the summation over of `diff[i][j] ` over all possible `i` and `j`\n\n```class Solution {\n    public int countSubstrings(String s, String t) {\n      int n = s.length();\n      int m = t.length();\n      \n      int[][] diff = new int[n][m];\n      int[][] id = new int[n][m];\n      int total = 0;\n      for (int i = 0; i < n ; i++) { \n        diff[i][0] = s.charAt(i) == t.charAt(0) ? 0 : 1;\n        id[i][0] = s.charAt(i) == t.charAt(0) ? 1 : 0;\n        total += diff[i][0];\n      }\n      for (int j = 0; j < m ; j++) { \n        diff[0][j] = s.charAt(0) == t.charAt(j) ? 0 : 1;\n        id[0][j] = s.charAt(0) == t.charAt(j) ? 1 : 0;\n        total += diff[0][j];\n      }\n      total -= diff[0][0]; //double counted\n      \n      for (int i = 1; i < n; i++) {\n        for (int j = 1; j < m; j++) {\n          if (s.charAt(i) == t.charAt(j)) {\n            diff[i][j] = diff[i-1][j-1];\n            id[i][j] = 1+ id[i-1][j-1];\n          } else {\n            diff[i][j] = 1 + id[i-1][j-1];\n            id[i][j] = 0;\n          }\n          total += diff[i][j];\n        }\n      }\n      return total;\n    }\n}\n\nBelow is the space optimised version of the same, we only need the previous row in each iteration\n\n```class Solution {\n    public int countSubstrings(String s, String t) {\n      int n = s.length();\n      int m = t.length();\n      int[][] diff = new int[m][2];\n      int[][] id = new int[m][2];\n      int total = 0;\n      for (int i = 0; i < n; i++) {\n        int now = i % 2;\n        int prev = 1 - now;\n        for (int j = 0; j < m; j++) {\n          if (s.charAt(i) == t.charAt(j)) {\n            diff[j][now] = j == 0 ? 0 : diff[j-1][prev];\n            id[j][now] = j == 0 ? 1 : 1 + id[j-1][prev];\n          } else {\n            diff[j][now] = j == 0 ? 1 : 1 + id[j-1][prev];\n            id[j][now] = 0;\n          }\n          total += diff[j][now];\n        }\n      }\n      return total;\n    }\n}
[]