ENGLISH Video Editorial - (Without Using Trie)

editorial
, , ,
1
8 Likes
2

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
3

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

1 Like
4

Great going brother😍

1 Like
5

Is your approach like this ?
My one without a trie - CodeChef: Practical coding for everyone (partial only :frowning: )

2 Likes
6

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
7

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
8

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

2 Likes
9

what is logic in this it is working due to loose testcases only.

10

Logic is that it’s working fine he used kind off greedy approach and hashing if you can see that .

1 Like
11

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

2 Likes
12

Yes.

13

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

1 Like
14

So Can you plz explain me your logic and implementation with complexity.

15

using trie see editorials for explanation

16

Its O(n^2) only, it’s just that the test cases weren’t strong enough so this approach worked fine.

2 Likes
17

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

18

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!

19

atleast someone there whos approach match… (partial submit) same approach… if you get bug of that approach share with me too. thanks

1 Like
20

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