C++/Java/Python3 O(n ^ 3) => O(n ^ 2)
I misread the description and got wrong answer first time. Then I got TLE as I tried to use a map or a trie. I thought about using a rolling hash, but it sounde
I misread the description and got wrong answer first time. Then I got TLE as I tried to use a map or a trie. I thought about using a rolling hash, but it sounded too complicated.\n\nFinally, I looked at the constraint and thought a simple cubic solution should do. We analyze all pairs of starting points in our strings (which is O(n ^2)), and the trick is to count substrings in a linear time.\n\n> Update: we can also count substrings in O(1) time if we precompute. Check approach 3 below.\n\n#### Approach 1: Compare and Expand\nWe compare strings starting from `s[i]` and `t[j]`, and track the number of mismatched characters `miss`:\n- 0: continue our comparison\n- 1: we found a substring - increment res and continue our comparison\n- 2: break from the loop.\n\n**C++**\n```cpp\nint countSubstrings(string &s, string &t) {\n    int res = 0;\n    for (int i = 0; i < s.size(); ++i) {\n        for (int j = 0; j < t.size(); ++j) {\n            int miss = 0;\n            for (int pos = 0; i + pos < s.size() && j + pos < t.size(); ++pos) {\n                if (s[i + pos] != t[j + pos] && ++miss > 1)\n                    break;\n                res += miss;\n            }\n        }\n    }\n    return res;\n}\n```\n**Java**\n```java\npublic int countSubstrings(String s, String t) {\n    int res = 0;\n    for (int i = 0; i < s.length(); ++i) {\n        for (int j = 0; j < t.length(); ++j) {\n            int miss = 0;\n            for (int pos = 0; i + pos < s.length() && j + pos < t.length(); ++pos) {\n                if (s.charAt(i + pos) != t.charAt(j + pos) && ++miss > 1)\n                    break;\n                res += miss;\n            }\n        }\n    }\n    return res;        \n}\n```\n\n**Python 3**\n```python\nclass Solution:\n    def countSubstrings(self, s: str, t: str) -> int:\n        res = 0\n        for i in range(len(s)):\n            for j in range(len(t)):\n                miss, pos = 0, 0\n                while i + pos < len(s) and j + pos < len(t) and miss < 2:\n                    miss += s[i + pos] != t[j + pos]\n                    res += miss == 1\n                    pos += 1\n        return res\n```\n**Complexity Analysis**\n- Time: O(n ^ 3), as we have three nested loops.\n- Memory: O(1).\n#### Approach 2: Process Missmatches\nAlternativelly, we can process all pair of missmatched characters `s[i]` and `t[j]`. Starting from the missmatch, we count matching characters to the left `l` and to the right `r`. The total number of substrings will be `l * r`.\n**C++**\n```cpp\nint countSubstrings(string &s, string &t) {\n    int res = 0;\n    for (int i = 0; i < s.size(); ++i)\n        for (int j = 0; j < t.size(); ++j) {\n            if (s[i] != t[j]) {\n                int l = 1, r = 1;\n                while (min(i - l, j - l) >= 0 && s[i - l] == t[j - l])\n                    ++l;\n                while (i + r < s.size() && j + r < t.size() && s[i + r] == t[j + r])\n                    ++r;\n                res += l * r;\n            }\n        }\n    return res;\n}\n```\n**Complexity Analysis**\n- Same as for approach above.\n#### Approach 3: Process Missmatches + DP\nThis is the same as approach 2 above, but we use DP to precompute sizes of a matching substring ending at position `[i][j]` (`dpl`), and starting from position `[i][j]` (`dpr`).\n**C++**\n```cpp\nint countSubstrings(string &s, string &t) {\n    int res = 0;\n    int dpl[101][101] = {}, dpr[101][101] = {};\n    for (int i = 1; i <= s.size(); ++i)\n        for (int j = 1; j <= t.size(); ++j)\n            if (s[i - 1] == t[j - 1])\n                dpl[i][j] = 1 + dpl[i - 1][j - 1];\n    for (int i = s.size(); i > 0; --i)\n        for (int j = t.size(); j > 0; --j)\n            if (s[i - 1] == t[j - 1])\n                dpr[i - 1][j - 1] = 1 + dpr[i][j];\n    for (int i = 0; i < s.size(); ++i)\n        for (int j = 0; j < t.size(); ++j)\n            if (s[i] != t[j])\n                res += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1);\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(n ^ 2), we have two nested loops to precompute sizes, and count substrings.\n- Memory: O(n ^ 2) for the memoisation.
[]