C++ O(n^2) solutioin - 4ms beat 100%
Idea is: for each (i, j) pair, where i in the index in s and j is the index in t, if they are not the same, we then basically need to calculate what is the long
Idea is: for each (i, j) pair, where i in the index in s and j is the index in t, if they are not the same, we then basically need to calculate what is the longest substring ends at s[i - 1] and t[j - 1] such that they are the same, and what is the longest substring starts at s[i + 1] and t[j + 1] such that they are the same. Then we can use combinatorics to determine how many valid substring pair that contains s[i] and t[j].\n\nSee code below (can be cleaned up a bit):\n```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        // dp[i][j] := longest substring ends at s[i] and t[j] such that they are equal\n\t\t// dp2[i][j] := longest substring starts at s[i] and t[j] such that they are equal\n        int m = s.length(), n = t.length();\n        vector<vector<int>> dp(m + 2, vector<int>(n + 2));\n        vector<vector<int>> dp2(m + 2, vector<int>(n + 2));\n        \n        {\n            dp[1][1] = s[0] == t[0];\n\n            for (int i = 1; i <= m; i++)\n                dp[i][1] = s[i - 1] == t[0];\n\n            for (int j = 1; j <= n; j++)\n                dp[1][j] = s[0] == t[j - 1];\n\n            for (int i = 2; i <= m; i++)\n                for (int j = 2; j <= n; j++) {\n                    if (s[i - 1] == t[j - 1])\n                        dp[i][j] = 1 + dp[i - 1][j - 1];\n                }\n        }\n        \n        {\n            dp2[m][n] = s[m - 1] == t[n - 1];\n            \n            for (int i = 1; i <= m; i++)\n                dp2[i][n] = s[i - 1] == t[n - 1];\n\n            for (int j = 1; j <= n; j++)\n                dp2[m][j] = s[m - 1] == t[j - 1];\n            \n            for (int i = m - 1; i >= 1; i--)\n                for (int j = n - 1; j >= 1; j--) {\n                    if (s[i - 1] == t[j - 1])\n                        dp2[i][j] = 1 + dp2[i + 1][j + 1];\n                }\n        }\n        \n        int res = 0;\n        \n        for (int i = 0; i < m; i++)\n            for (int j = 0; j < n; j++) {\n                if (s[i] != t[j]) {\n                    res += (dp[i][j] + 1) * (dp2[i + 2][j + 2] + 1);\n                }\n            }\n\n        return res;\n        \n    }\n};\n```
[]