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

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)

[AP-ehgr]

well explained. a bit of a struggle for the right words or variable name at times but I got the intuition alright

[yashpadiyar]

Bhaiya companies would be visiting my cllg from July onward for hiring interns jst want to know that when it comes to online assessment of major companies whose contest are more relevant leetcode's or codeforces, plss reply bhaiya and are leetcode contests enough