JoJo&Bizarre Adventure

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(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(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 :star_struck: