Problem link: CodeChef: Practical coding for everyone
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- Smallest window in a String containing all characters of other String - GeeksforGeeks
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(nlogn) 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(nlogn) which is sufficient to pass the given constraints.
You can refer to this if you feel the need to do so - CodeChef: Practical coding for everyone
1 Like
thanks man…i got it 