Problem link: https://www.codechef.com/CSEP2020/problems/JOJOA

I need help with approach to solve the problem. As i have n^2 solution but that won’t work after seeing the large constraints.

Problem link: https://www.codechef.com/CSEP2020/problems/JOJOA

I need help with approach to solve the problem. As i have n^2 solution but that won’t work after seeing the large constraints.

Learn sliding window technique.

Link for the same question- https://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/amp/

1 Like

this gfg code has (n^2) worst case time complexity. As outer 'for ’ loop is running n times and inner 'while ’ loop runs for around n times in worst case , and thus has n^2 time complexity…but why it is getting accepted as n <=10^6…please help

You can solve this question in O(n*logn) using a binary search on the answer.
Suppose you want to know that whether length x is a valid answer or not then you can do that in O(n) by using a sliding window technique, and we know that x is lower bounded by 0 and upper bounded by n (n is the length of the string). Hence Binary search on these n values along with checking for a particular value that whether it can be an answer or not will result in the total complexity of O(n*logn) which is sufficient to pass the given constraints.

You can refer to this if you feel the need to do so - https://www.codechef.com/viewsolution/37788905

1 Like

thanks man…i got it