L4. Number of Distinct Substrings in a String | Trie | C++ | Java

[@takeUforward]

Lets start a new trend, please comment "understood" in case you did :)

[@siddharthsingh991]

Always avoided Trie concept, but after watching your videos I have started thinking if a particular problem can be solved using Trie DS or not. Haha ! Great Content, keep it up..

[@shreyanshmittal9381]

Understood it very well. Pretty simple implementation, was able to code it myself upon seeing the explanation! Thanks a lot raj bhaiya❤

[@sakshampandit1335]

sir there is a mistake in your code "instead of word[i] you should have written word[j] in every function you have passed" it will not execute properly..

[@techdemy4050]

@take U forward what if I use unordered_map mp instead of using links[26] does space complexity will be O(n^2) in the worst case scenario. Please correct me if I am wrong

[@sohamsen7892]

Same query

[@thinkingmad1685]

Use map then worst case will be nlogn

[@_-6912]

understood and its clever way of implementation.

[@vidhishah9154]

Understood, Thanks for making hard things easy.

[@lavanya_m01]

Brilliant approach!

[@your_name96]

Imp : if multiple words are not given, no need to construct explicit trie class

[@abhayj8706]

Please start dp series only you can teach best 🙏🙏🙏🙏💯

[@yogendrajhala4147]

Bro check aditya dp series, it will help u

[@Rohitkumar-ks9io]

@@yogendrajhala4147 Yes I agree!! Aditya Verma is like DP God

[@satyampande684]

I tried to solve the problem given in the problem link but I am getting TLE as a verdict and in question, it is specifically written that we have to implement the trie method. Is there any more approach better than this one?

[@takeUforward]

Hashing

[@sarthak7438]

I'm not getting tle with trie approach

[@satyampande684]

@@sarthak7438 Yes, I think they have increased time limit or decreased test cases. Same code got TLE 6th months before but now it's showing correct answer.

[@rushidesai2836]

Thanks Striver!

[@UECAshutoshKumar]

Thank you 🙏

[@mohitsingh7793]

Avoid String hashing it will give u MLE when string length is very large.

[@nishankdeep3084]

understood bhaiya thank you bhaiya

[@bhai-bm4kj]

Understood bhaiya

[@coderhat1980]

understood great explaination. But I have one more doubt I am able to submit the answers , but its showing TLE. can we reduce the O(n2) complexity?

[@azeezmoiz9195]

use suffix arrays

[@tukaighosh4383]

Understood.. But couldn't understand why you mentioned time complexity of set.add() as logN at 4:11 . As we know that HashSet has amortized time complexity as O(1) for add operation as it uses hashmap internally. I'm assuming that hash collision will rarely occur. Again I would say you explained it very well.

[@takeUforward]

Unordered set has, not set

[@mevam123]

So why we used set here and not the unordered set?

[@tusharvlogs6333]

@@mevam123 absolutely what i was thinking of. we only need the substrings, order doesn't matter to us so we can use unordered_set

[@ar3568row]

@adolft_official and so is the case with Trie, I think Trie doesn't improve the time complexity over unordered_set, it only improves the space complexity.

[@priyanshkumar17]

@@tusharvlogs6333 yes

[@mohitsanjaymahajan3246]

Using unordered_set it will be N^2 so i think no need to use trie?

[@anujtyagi4047]

use unordered set instead of set

[@wolfrikz7238]

understood, great explanation ❤️

[@manoharmanu9240]

Understood 🙌

[@Harsh-pv7pb]

Is there any O(n) solution present for this??

[@SurajSingh-kd8gw]

Is creating trie class important ? Like in last question u did it, so can we solve that without creating it

[@sanjuchandra9405]

for those who are getting memory limit error in leetcode: const int MAX_NODES = 500 * 500; // Maximum number of nodes in the trie (based on the problem constraints) int trie[MAX_NODES + 5][26]; // Trie data structure: Each node can have up to 26 children (corresponding to letters 'a' to 'z') class Solution { public: int countDistinct(string &str) { int n = str.size(); // Length of the input string int ans = 0; // Count of distinct substrings int sz = n * n * 26 * sizeof(int); // Size of memory to initialize trie memset(trie, 0, sz); // Initialize trie with zeros int root = 0; // Root of the trie int temp = root; // Temporary variable to traverse the trie // Loop over all substrings of the input string for (int i = 0; i < n; i++) { // Start building substrings from index i for (int j = i; j < n; j++) { int d = str[j] - 'a'; // Calculate the index corresponding to the character // Access the child node 'd' of the current node 'temp' in the trie int &pos = trie[temp][d]; if (pos == 0) { // If the child node doesn't exist (not visited before), create a new node ans++; // Increment the count of distinct substrings pos = ans; // Link the new node with its parent } // Move to the next node in the trie (corresponding to the character 'd') temp = pos; } // Reset temp to root for the next substring starting from index i+1 temp = root; } return ans; // Return the total count of distinct substrings } };

[@hemantvardani1436]

Thanks

[@utkarsh_108]

understooooood. thanks bhaiya 🙂

[@devendrapatil07]

Node* links[26] ; These array has default value of NULL?

[@shubhrajit2117]

At 4:06 I searched the time complexity of set operations and it said O(1) for avg case and O(N) for worst case.

[@tusharvlogs6333]

why did the loop run till n-1 for the brute approach. shouldn't it run till n times. because we also need to consider the last ele of the string.

[@prasadjambhale]

Its basically less than equal to n - 1 for(int j = 0; j

[@Electrocode_gk]

i =0 bakwas

[@sivaganesh4489]

Thanks dude

[@arihantjammar8888]

Understood 😊

[@bhai-bm4kj]

Love you sir

[@tanujsharma2874]

can you plz tell me the board name you are using ?

[@Yash-uk8ib]

sir, why is space complexity of the brute soln O(n*n) * O(n) ? why is string length taken into account?? why is it not correct to say that it takes O(n*n) space?

[@vishalgupta957]

because the average length of substring is n/2 on an average. there can be substring of size 1 as well and substring of size n as well so it averages out to be n/2 for each substring. Cheers :)

[@abhinavsingh6532]

@@vishalgupta957 but to insert a string in unordered_set take O(1) then it must be O(n^2) only ?

[@vishalgupta957]

@@abhinavsingh6532 nope it's amortized O(1)

[@jolly_dollyyy]

understood!!

[@ashishsachan08]

Great...Thanks..

[@arahul6098]

understood..

[@anshulgoel1940]

Understood but why do we need a set here to strings at 4:11

[@sohamsen7892]

Understood

[@shubhamkumar1305]

Sir, there is something wrong during you write code same code I written in python , but we try test case "ninja" it should be return 15 (14 + 1), but answer is not getting right.

[@Agent47_live]

what teaching app are you using?

[@anuragsahay9944]

an OA asked to solve it in O(NLogN). Len(string) was 1e5.

[@AmandeepSingh-uq3wp]

understood

[@satwiktatikonda764]

how the worst case tc for adding to set takes logm..if there are collisions it becomes o(m) right ? can anyone explain

[@greedycat9845]

understood😁

[@satyampande684]

Understood!!

[@sagarbora7768]

same content i learned in masterclass

[@aakashparmar560]

Understood!!!

[@DebashishGhoshOfficial]

The average length of a sub-string of a non-empty string of length n is (n + 2) / 3.

[@remmargorpp]

wouldn't that be word[j] in the second for loop?

[@takeUforward]

You can check the github code once… its running and accepted one

[@remmargorpp]

@@takeUforward yep the github code is errorless! Thank you for the reply.

[@takeUforward]

@@remmargorpp yes since i was typing live, might just have done a typo. Thanks.

[@champion5946]

UnderStood

[@souravchakraborty9777]

Other than TRIE how to solve this problem? Would you kindly tell me the answer?

[@Sandeepg255]

via suffix array

[@rahulsrivastava9710]

Time limit exceeded... ???

[@visheshagrawal8676]

working code without trie if someone needs : #include int countDistinctSubstrings(string &s) { int ans = 0; unordered_setst; for( int i = 0 ; i < s.size() ;i++){ string temp = ""; for( int j = i ; j < s.size() ; j++){ temp +=s[j]; st.insert(temp); } } return st.size()+1; }

[@AlokYadav-SKB]

Ask your viewers to click on youtube Icon/Text then only they would be able to see Like and comment option.

[@addityasharma6426]

understood :-)

[@shradhaydham4745]

why don't we need trie class here?

[@vanshchaudhary8291]

US

[@shivampathak1371]

In code, line 4

[@mkat21]

Sir question link thoda ur chupa Kar rakh date

[@himanshuagarwal1066]

Bro you mentioned i and putting index i instead of j that was wrong bro

[@GyaneshTiwari-dw4zb]

understood ++

[@akashsahu2571]

cfbr

[@amborishnath7755]

us

[@ssss-mv6dx]

Why are we doing the get? what is the need to check the containsKey?

[@user-tj3us8il6f]

**********Where r more opportunities for a tier 3 college guy(in terms of getting interview call) in well funded start ups or big MNCs***********

[@vishalgupta957]

level up your DSA you will get interview calls from both. Happy Coding :)

[@VinayKumar-ze2ww]

Understood

[@nikhiltiwari33]

understood

[@meghamaheshwari4445]

Understood!

[@gautamgrover1087]

us

[@nithinnarayanansaravanan7792]

Understood

[@LevelUpJourney-d2d]

understood

[@jaiminsolanki5478]

Understood!

[@studybits1604]

us

[@codingp110]

Understood!

[@deepakkarki461]

Understood

[@prashant33333]

understood

[@umeshkaushik710]

Understood

[@rounakjoshi6680]

understood

[@nopecharon]

Understood

[@dubai67003]

understood

[@chandrachurmukherjeejucse5816]

Understood.

[@yashjain1492]

understood

[@lingasodanapalli615]

Understood

[@prashantdubey4112]

understood

[@sukhpreetsingh5200]

understood

[@komalyadav5599]

Understood

[@NARUTOUZUMAKI-bk4nx]

Understood

[@rohitchoudhari5441]

understood

[@engineer8340]

understood

[@manojnavinjamuri5867]

understood

[@Sillysmiles76]

understood

[@javierdavidhernandezestrad7334]

understood

[@manideepdeepnaidugorle7308]

understood

[@shaiksoofi3741]

understood

[@tanishkumar6682]

understood

[@tsharmi919]

understood