I thought of this approach till removing identical words and keep only word with freq 1 but since I was trying to make complexity less than O(n^2
) so I never though of proceeding in this way further.
Thanks for crystal clear explanation.
I will try to implement this logic now.
@xxy_xxy Please help me grow this channel by sharing, liking, subscribing! Thanks.
Great going brother😍
Is your approach like this ?
My one without a trie - https://www.codechef.com/viewsolution/28960045 (partial only )
Can you explain why traversing over the words array in a nested manner won’t give a TLE? How can it be proved that after removing the duplicate strings the remaining strings would be so less that a O(n^2) algorithm can be run on them?
I tried implementing his solution and it’s running absolutely fine in O(N^2).
Thanks for great Explanation also for the nice and simple approach for implementing the solution @som_s_mukherji
@nuttela you can check
here the c++ implementation https://www.codechef.com/viewsolution/28984587
Keep the hard work going you’re doing great !!!
what is logic in this it is working due to loose testcases only.
Logic is that it’s working fine he used kind off greedy approach and hashing if you can see that .
In worst case if all the strings are different then it will not work because simply its O(n^2) implementation afterall.
i am still surprised that it worked(codechef things).
So Can you plz explain me your logic and implementation with complexity.
using trie see editorials for explanation
Its O(n^2) only, it’s just that the test cases weren’t strong enough so this approach worked fine.
I think it is more than O(n^2) . … two loops for all the combinations + check method in b/w them for comparing 2 strings((Maybe I am wrong))… (also, maybe you can reduce the no. of comparisons by running inside loop from j=i+1) …But this is a good way maybe useful in future competition…(thanks for doing it in Python ).
Ya Exactly I should have done the inner loop from “i+1”. I recorded it in one go, so I missed it, anyways Nice Observation!
atleast someone there whos approach match… (partial submit) same approach… if you get bug of that approach share with me too. thanks
I did not code this logic because I was sure it won’t get AC.