Subsequence With the Minimum Score | O(n) | Leetcode 2565 | Weekly contest | DSA | Think then Code

Problem Link - https://leetcode.com/problems/subsequence-with-the-minimum-score/description/ Timestamps: 00:00 Question Explanation 01:20 Intuition/Observation 04:32 Algorithm Dry Run 19:43 Code 24:40 Time and Space Complexity Intuition If right - left + 1 is the cost (this is similar to size of substring from left to right index), there is no sense in removing only some elements from left index to right index. It makes sense to remove entire substring. Because then we will be having a smaller string t to form a subsequence which is better. So we will remove all characters from left index to right index. Which means we will will remove a substring from t. Now about right and left: I can build all possible left separately and then for a particular right, I can get a left(which I previously built) to form answer. Approach First we start to build all possible left. How? We keep two pointers ps(for s string) and pt(for t string) We initialize both to 0. We keep incrementing ps pointer until value at both pointers are not equal In other words, until substring of t from 0 - pt doesn't become a subsequence of (substring of s from 0 - ps). Once this done we add {pt+1, ps} to our possible left vector. Why pt+1? Becuse that is the left Why ps? We are storing s index for all possible left because it can happen that s index for right becomes less than or = the s index for left. In that case our answer will be wrong. Then we start our process to get right: In the same way we build possible left from start of our array, we get possible rights from end of the array There just two differences here: We keep eliminating elements from back of the possible left array based on two conditions: i. left less than or = right ii. s index for left should be less than s index for right We calculate answer for substring left--right Have a look at code for better understanding. Complexity Time complexity: O(n) Space complexity:O(n)