# 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

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 )

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 !!!

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

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.