C++ || EASY TO UNDERSTAND || 3 Appraches
Time Complexity O(NxNxN)\n\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans=0;\n        int n=s.length();\n        int
**Time Complexity O(NxNxN)**\n```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans=0;\n        int n=s.length();\n        int m=t.length();\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<m;j++)\n            {\n                if(s[i]!=t[j])\n                {\n                    int left=1,right=1;\n                    while(i-left>=0&&j-left>=0&&s[i-left]==t[j-left])\n                    {\n                        ++left;\n                    }\n                    while((i+right)<n&&(j+right)<m&&s[i+right]==t[j+right])\n                    {\n                        ++right;\n                    }\n                    ans+=(left*right);\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n**Another Approach with The Same Time Complexity**\n```\nclass Solution {\npublic:\n    int countSubstrings(string s, string t) {\n        int ans=0;\n        int n=s.length();\n        int m=t.length();\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<m;j++)\n            {\n                int miss=0;\n                for(int p=0;i+p<n&&j+p<m;p++)\n                {\n                    if(s[i+p]!=t[j+p])\n                    {\n                        miss++;\n                        if(miss>=2)\n                        break;\n                    }\n                    ans+=miss;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n**DP approach T.C. O(s.size()Xt.size())**\n```\nclass Solution {\npublic:\n    int countSubstrings(string &s, string &t) {\n    int res = 0;\n    int dp1[101][101] = {}, dp2[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                dp1[i][j] = 1 + dp1[i - 1][j - 1];\n    \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                dp2[i - 1][j - 1] = 1 + dp2[i][j];\n    \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 += (dp1[i][j] + 1) * (dp2[i + 1][j + 1] + 1);\n    \n    return res;\n  }\n};\n```\n**Please upvote to motivate me in my quest of documenting all leetcode solutions(to help the community). HAPPY CODING:)\nAny suggestions and improvements are always welcome**
[]