This Problem Drove me Crazy! Stayed up from 4 A.M. to 10 A.M. solving this.
I couldn\'t solve the problem during the contest, but I didn\'t want to read any solutions because it seemed solvable. But as the night progressed, I began to t
I couldn\'t solve the problem during the contest, but I didn\'t want to read any solutions because it seemed solvable. But as the night progressed, I began to think it was impossible. Here are the ideas of my failed approaches:\n\n**Approach 1: Binary Search on Length of Optimal R-L**\nThe idea was to use binary search to find the optimal length of R-L. Whenever I encountered a character that could not form a subsequence, I skipped the next [mid] elements. This is the approach I tried during the contest, which only passed ~30 test cases. I assumed this was due to bad implementation, so I continued this approach for 2 more hours.\n**Why It Didn\'t Work:**\nI looked over the fact that sometimes it is not always optimal to start deleting at the first element that doesn\'t fit. For example, for the case "abcdef" "afbcde", my program would go from a to f then delete b, c, d, and e. This is not optimal.\n\n**Approach 2: Sliding Window + Binary Search**\nThe idea was basically the same as the first one but with a sliding window of length [mid]. I couldn\'t figure out how to check if the sequence t was a subsequence of s with a sliding window in O(N) time however, so this approach died because it was O(N^2 log N) at best.\n\n**Approach 3: Binary Search on Right and Left Bound**\nThis time, I tried to do two separate binary searches. The first one was to find the leftmost right index that I would have to delete up to to make t a subsequence of s. Then, I would find minimum distanced left index from right that would still allow the subsequence condition to be fulfilled. This would be found using a second binary search.\n**Why It Didn\'t Work:** \nIt turns out finding the minimum right index was basically irrelevant. While I do find the minimum right bound, it doesn\'t guarantee that the left bound created from it is optimal.\n\n**Approach 4: DP + Binary Search (Accepted!!)**\nFinally! I had the idea to use DP and binary search to find the optimal right and left bound. Scan string t from the left and right and record the most characters you can use from the left and right. Then use binary search to find the maximum non-overlapping sum.\n\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        map<int, int> m;\n        int p1 = 0; // pointer for string s\n        int ans = 0;\n        for(int i = 0; i < t.length(); i++){\n            while(p1<s.length() && t[i] != s[p1]) p1++;\n            if(p1 == s.length()) break;\n            m[p1] = i+1; // how many characters I can use up to this point\n            p1++;\n            ans = max(ans, i+1);\n        }\n        p1 = s.length()-1;\n        for(int i = t.length()-1, k =1; i>=0; i--, k++){\n            while(p1>=0 && t[i] != s[p1]) p1--;\n            if(p1<0) break;\n            auto it = m.lower_bound(p1);\n            if(it != m.begin()){ // find the best non overlapping pointer behind this one and add it up\n                it--;\n                auto other = it->second;\n                ans = max(ans, k+other);\n            }\n            p1--;\n            ans = max(ans, k);\n        }\n        int len = t.length();\n        if(len-ans<0) return 0;\n        return len-ans;\n    }\n};\n
[]