ENGLISH Video Editorial - (Without Using Trie)

7 Likes

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.

1 Like

@xxy_xxy Please help me grow this channel by sharing, liking, subscribing! Thanks.

1 Like

Great going brother😍

1 Like

Is your approach like this ?
My one without a trie - https://www.codechef.com/viewsolution/28960045 (partial only :frowning: )

2 Likes

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?

1 Like

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

1 Like

Keep the hard work going you’re doing great !!!:blue_heart:

2 Likes

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 .

1 Like

In worst case if all the strings are different then it will not work because simply its O(n^2) implementation afterall.

2 Likes

Yes.

i am still surprised that it worked(codechef things).

1 Like

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.

2 Likes

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 :slight_smile: ).

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

1 Like

I did not code this logic because I was sure it won’t get AC.
My bad.