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.
Great going brotherđ
Is your approach like this ?
My one without a trie - CodeChef: Practical coding for everyone (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.
Yes.
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.
My bad.