Someone tell its approach
String Window problem
hello @devesh20500
The question asks us to return the minimum window from the string SS which has all the characters of the string TT. Let us call a window desirable if it has all the characters from TT.
We can use a simple sliding window approach to solve this problem.
In any sliding window based problem we have two pointers. One rightright pointer whose job is to expand the current window and then we have the leftleft pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.
The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.
The answer is the smallest desirable window.
Algorithm
- We start with two pointers, leftleft and rightright initially pointing to the first element of the string SS.
- We use the rightright pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of TT.
- Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.
- If the window is not desirable any more, we repeat step 2 onwards.
1 Like
Still getting wrong answer in some test cases. Did it happen with anyone else?
well if its giving wrong maybe it doesn’t account for all cases you must be doing something wrong @devesh20500
Also i can see you have already got 100 points in your code earlier so if your doubt is cleared dont forget to mark it resolved
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.