C# | Combinations | Left and right choices -> combination
April 14, 2022\nIntroduction\nIt takes me three steps to understand the problem, first I read the problem statement and test cases, but I was not sure what to a
April 14, 2022\n**Introduction**\nIt takes me three steps to understand the problem, first I read the problem statement and test cases, but I was not sure what to ask for; I read the analysis done by one most voted discuss post, votrubac, and I did not follow; so I studied the code and then wrote C# code, and I understood the analysis and how to solve it. I will write down my own explanation. \n\n**Analsysis | My explanation**\nI just quickly copied one analysis with an example in the following:\nIntuition: We can find each pair of s[i] != t[j]. Then try to extend both sides when s[i + t] == t[j + t]. If we have left steps extended on the left side and right steps on the right side, we have (left + 1) * (right + 1) options for this { i, j } case.\n\nExample:\n\ns = xbabc\nt = ybbbc\nFor i = 2 and j = 2, we have s[i] = a and t[j] = b that doesn\'t match. Now look leftwards, we can extend left-side by 1 time due to b, and extend right-side by 2 times due to bc. So for this specific center { i = 2, j = 2 }, we have 2 * 3 = 6 options.\n\nIn total, the count of substring is 32. But i = 2 and j = 2, substring of s can start from "ba" or "a" two options, and can end in three options, "a", "ab", "abc"; substring of t can start from "bb" or "b", end with "b" or "bb" or "bbc". So it is multiplication of left variable and right variable. \n\n**My explanation**\nIt takes a few minutes for me to figure out the above example\'s answer is 2 * 3 = 6 options. Why?\nLeft side substring only has options which is the length of left variable. \n\nThe following C# code passes online judge. \n\n```\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Text;\nusing System.Threading.Tasks;\n\nnamespace _1638_countSubstrings\n{\n    class Program\n    {\n        static void Main(string[] args)\n        {\n             //var result = CountSubstrings("aba", "baba");\n            var result = CountSubstrings("xbabc", "ybbbc");\n            Debug.Assert(result == 32);\n        }\n\n        /// <summary>\n        /// study code\n        /// https://leetcode.com/problems/count-substrings-that-differ-by-one-character/discuss/917690/C%2B%2B-O(N3)-with-explanation\n        /// Time complexity: O(N^3)\n        /// </summary>\n        /// <param name="s"></param>\n        /// <param name="t"></param>\n        /// <returns></returns>\n        public static int CountSubstrings(string s, string t)\n        {\n            if (s == null || t == null)\n            {\n                return 0; \n            }\n\n            var sLength = s.Length;\n            var tLength = t.Length;\n            var combinations = 0;\n\n            for (int i = 0; i < sLength; ++i)\n            {\n                for (int j = 0; j < tLength; ++j)\n                {\n                    if (s[i] == t[j])\n                    {\n                        continue;\n                    }\n\n                    int left = 1;\n                    var right = 1;\n\n                    while (i - left >= 0 && j - left >= 0 && s[i - left] == t[j - left])\n                    {\n                        ++left;\n                    }\n\n                    while (i + right < sLength && j + right < tLength && s[i + right] == t[j + right])\n                    {\n                        ++right;\n                    }\n\n                    combinations += left * right;  // including one char substring \n                }\n            }\n\n            return combinations;\n        }\n    }\n}\n```
[]