Simple Binary Search and Prefix Solution || C++
Approach\n Describe your approach to solving the problem. \nWe need to find longest prefix subseq in s and also suffix subseq in s. And we now have to cross che
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe need to find longest prefix subseq in s and also suffix subseq in s. And we now have to cross check for every value if we have non overlapping substring of t in both prefix and suffix then we will see right and left according to prefix and suffix and compare it with our answer .\n# Complexity\n- Time complexity: O(NLogN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int st = t.length();\n        vector<int> r, l;\n        for(int i=0, j = 0;i<t.length() && j < s.length();j++){\n            if(s[j] == t[i]){ l.push_back(j); i++;}\n        }\n        for(int i=t.length()-1, j = s.length()-1;i>=0 && j>=0;j--){\n            if(s[j] == t[i]){ r.push_back(j); i--;}\n        }\n        reverse(r.begin(),r.end());\n        int ans = t.length();\n        // if we do not have any prefix subseq then we have left = 0 and right equal to t len - rsize\n        // see cdeaaaa , bzxcaaaa\n        // aaaa is common so r size is 5 right here is 3 \n        // so 8 - 4 = 4;\n        int l0 =  t.length() - r.size(); // if left size is 0\n        int r0 =  t.length() - l.size(); // if right size is 0\n        // similarly\n        // aaaabzxc\n        // aaaa is common so l size is 4 and left is 4 and right is t.len - 1\n        if(l.size() == t.length() || r.size() == t.length()) return 0;\n        // if we have both side s = acdfgaaaa , t = cfghghgaaaa\n        // l = cfg , r = gaaaa , here we can see we have used same g 2 times\n        ans = min({ans,l0,r0});\n        for(int i=0;i<l.size();i++){\n            // Now we have to see for this index\n            int ind = upper_bound(r.begin(),r.end(),l[i]) - r.begin();\n            ind = r.size()-ind; // we got right side longest length\n            ind = t.length()-ind-1; // now we need right value so we need to subtract t len to ind\n            ans = min(ans,ind - i);\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Prefix Sum', 'C++']