97% TC and 95% SC easy python solution with explanation
Believe me, this ques is like must to have in the mind, as this gonna help you solve many such questions.\n1. We have to calculate all substrings which differ b
Believe me, this ques is like must to have in the mind, as this gonna help you solve many such questions.\n1. We have to calculate all substrings which differ by just a character.\n2. So, maintain 2 states, first one will be for the count of substrings which is present in "t" string as well(all characters equal). The second one will keep the count with 1 different character.\n3. Traverse the 2 strings using 2 pointers using 2 loops. If the char which are being pointed are same, which means we will have our ans from already differed strings, which already have a character different. So just use that.\n4. If they are different, then go for all the strings which have all the characters same, because the current is gonna be a different one.\n5. Now just keep maintaining these 2 states for all the indices.\n6. Didn\'t get it, read it for 3-4 times atleast. And you\'re free to comment down :)\n```\ndef countSubstrings(self, s: str, t: str) -> int:\n\tls, lt = len(s), len(t)\n\tequal_prev, unequal_prev = [0] * (lt+1), [0] * (lt+1)\n\tans = 0\n\tfor i in range(ls):\n\t\tequal_curr, unequal_curr = [0] * (lt+1), [0] * (lt+1)\n\t\tfor j in range(lt):\n\t\t\tif(s[i] == t[j]):\n\t\t\t\tequal_curr[j+1] = 1+equal_prev[j]\n\t\t\tunequal_curr[j+1] = 1+equal_prev[j] if(s[i] != t[j]) else unequal_prev[j]\n\t\t\tans += unequal_curr[j+1]\n\t\tequal_prev, unequal_prev = equal_curr, unequal_curr\n\treturn ans\n```
['Dynamic Programming', 'Python', 'Python3']