Get Left for Right with Video || O(n) Time and Space || C++ Code
Intuition\nIf right - left + 1 is the cost (this is similar to size of substring from left to right index),\nthere is no sense in removing only some elements fr
# Intuition\nIf right - left + 1 is the cost (this is similar to size of substring from left to right index),\nthere is no sense in removing only some elements from left index to right index.\nIt makes sense to remove entire substring.\nBecause then we will be having a smaller string t to form a subsequence which is better.\n\nSo we will remove all characters from left index to right index.\nWhich means we will will remove a substring from t.\n\nNow about right and left:\n\nI can build all possible left separately and then for a particular right, I can get a left(which I previously built) to form answer.\n\nVideo:\n<iframe width="460" height="250" src="https://www.youtube.com/embed/c75mRQfNtxg" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n# Approach\nFirst we start to build all possible left.\nHow?\nWe keep two pointers ps(for s string) and pt(for t string)\nWe initialize both to 0.\nWe keep incrementing ps pointer until value at both pointers are not equal\n\nIn other words, until substring of t from 0 - pt doesn\'t become a subsequence of (substring of s from 0 - ps).\n\nOnce this done we add {pt+1, ps} to our possible left vector.\n\nWhy pt+1?\nBecuse that is the left\n\nWhy ps?\nWe are storing s index for all possible left becuase it can happen that s index for right becomes <= the s index for left.\nIn that case our answer will be wrong.\n\nThen we start our process to get right:\n\nIn the same way we build possible left from start of our array, we get possible rights from end of the array\n\nThere just two differences here:\n1. We keep eliminating elements from back of the possible left array based on two conditions:\n    i. left <= right\n    ii. s index for left < s index for right\n2. We calculate answer for substring left--right\n\nHave a look at code for better understanding.\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity:O(n)\n\n# C++ Code\n```\nclass Solution {\npublic:\n\tint minimumScore(string s, string t) {\n\t\tvector<pair<int, int>> psbLeft;// <left, s index for that left>\n\t\tint ps = 0;//pointer for s string\n\t\tint pt = 0;//pointer for t string\n\t\tint ans = t.size();\n\n\t\t//Building Possible Left:\n\t\tpsbLeft.push_back({0, -1});\n\t\twhile (ps < s.size() && pt < t.size()) {\n\t\t\twhile (ps < s.size() && s[ps] != t[pt])\n\t\t\t\tps++;\n\t\t\tif (ps == s.size())\n\t\t\t\tbreak;\n\t\t\tpsbLeft.push_back({pt + 1, ps});\n\t\t\tpt++;\n\t\t\tps++;\n\t\t}\n\n        //If t is subsequence of s then we return 0\n        //If not we can get smallest substring from end of t we have to remove to make t substring of s\n\t\tif (psbLeft.back().first == t.size())\n\t\t\treturn 0;\n\t\telse\n\t\t\tans = min(ans, (int)t.size() - psbLeft.back().first);\n\n\t\tps = s.size() - 1;\n\t\tpt = t.size() - 1;\n\n        //Getting Possible Right\n\t\twhile (ps >= 0 && pt >= 0) {\n\t\t\twhile (ps >= 0 && s[ps] != t[pt])\n\t\t\t\tps--;\n\t\t\tif (ps < 0)\n\t\t\t\tbreak;\n\n\t\t\tint right = pt - 1;\n\n            //Two conditions checked in below code:\n            //1. left <= right\n            //2. s index for left < s index for right\n\t\t\twhile (psbLeft.size() && (psbLeft.back().first > right || psbLeft.back().second >= ps))\n\t\t\t\tpsbLeft.pop_back();\n\n            //If substring from starting of t removed \n\t\t\tans = min(ans, pt);\n\n            //Left and right both used:\n\t\t\tif (psbLeft.size()) {\n\t\t\t\tint left = psbLeft.back().first;\n\t\t\t\tans = min(ans, right - left + 1);\n\t\t\t}\n\t\t\tpt--;\n\t\t\tps--;\n\t\t}\n\t\treturn ans;\n\t}\n};\n```\n<b>Upvote if you found this helpful!</b>
['Greedy', 'Sliding Window', 'C++']