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

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Lecture notes/C++/Java Codes - takeuforward.org/data-structu...
Pre-requisite: First Video of the Playlist: • L1. Implement TRIE | I...
In this video, we discuss the question counting the number of distinct substrings in a string.
Please share this channel as much as you can. Also, it's an earnest request to drop a comment "understood" if you are watching this video, so that I get to know you understood from this video.
SDE-Sheet/Linkedin/Telegram/Instagram: linktr.ee/takeUforward
-------------------------------------------------------------------------------------------------------------
Problem Link: bit.ly/3ocRQW0

[@takeUforward]

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

[@shreyanshmittal9381]

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

[@vidhishah9154]

Understood, Thanks for making hard things easy.

[@_-6912]

understood and its clever way of implementation.

[@lavanyam3224]

Brilliant approach!

[@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

[@wolfrikz7238]

understood, great explanation ❤️

[@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..

[@ashishsachan08]

Great...Thanks..

[@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

[@jolly_dollyyy]

understood!!

[@rushidesai2836]

Thanks Striver!

[@nishankdeep3084]

understood bhaiya
thank you bhaiya

[@mohitsingh7793]

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

[@manoharmanu9240]

Understood 🙌

[@UECAshutoshKumar]

Thank you 🙏

[@sivaganesh4489]

Thanks dude

[@utkarsh_108]

understooooood. thanks bhaiya 🙂

[@devendrapatil07]

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

[@your_name96]

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

[@aakashparmar560]

Understood!!!

[@meghamaheshwari4445]

Understood!

[@satyampande684]

Understood!!

[@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

[@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.

[@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.

[@greedycat9845]

understood😁

[@hemantvardani1436]

Thanks

[@arihantjammar8888]

Understood 😊

[@bhai-bm4kj]

Love you sir

[@AmandeepSingh-uq3wp]

understood

[@sohamsen7892]

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

[@chandrachurmukherjeejucse5816]

Understood.

[@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.

[@priyanshkumariitd]

@@tusharvlogs6333 yes

[@tanujsharma2874]

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

[@Harsh-pv7pb]

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

[@anujtyagi4047]

use unordered set instead of set

[@arahul6098]

understood..

[@addityasharma6426]

understood :-)

[@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

[@Coder_421]

i =0 bakwas

[@SurajSingh-kd8gw]

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

[@anshulgoel1940]

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

[@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.

[@DebashishGhoshOfficial]

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

[@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)

[@sagarbora7768]

same content i learned in masterclass

[@Agent47_live]

what teaching app are you using?

[@souravchakraborty9777]

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

[@Sandeepg255]

via suffix array

[@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
}
};

[@GyaneshTiwari-dw4zb]

understood ++

[@rahulsrivastava9710]

Time limit exceeded... ???

[@champion5946]

UnderStood

[@vanshchaudhary8291]

US

[@shivampathak1371]

In code, line 4

[@yogeshvaishnav7856]

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

[@takeUforward]

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

[@yogeshvaishnav7856]

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

[@takeUforward]

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

[@amborishnath7755]

us

[@mkat21]

Sir question link thoda ur chupa Kar rakh date

[@shradhaydham4745]

why don't we need trie class here?

[@AlokYadav-SKB]

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

[@himanshuagarwal1066]

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

[@akashsahu2571]

cfbr

[@LowkeyCoder]

"Understood"

[@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 :)

[@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;
}

[@jaiminsolanki5478]

Understood!

[@nikhiltiwari33]

understood

[@VinayKumar-ze2ww]

Understood

[@gautamgrover1087]

us

[@codingp110]

Understood!

[@nithinnarayanansaravanan7792]

Understood

[@deepakkarki461]

Understood

[@nbavideos4487]

understood

[@rounakjoshi6680]

understood

[@prashant33333]

understood

[@dubai67003]

understood

[@nopecharon]

Understood

[@sukhpreetsingh5200]

understood

[@lingasodanapalli615]

Understood

[@umeshkaushik710]

Understood

[@yashjain1492]

understood

[@komalyadav5599]

Understood

[@NARUTOUZUMAKI-bk4nx]

Understood

[@rohitchoudhari5441]

understood

[@engineer8340]

understood

[@manojnavinjamuri5867]

understood

[@Sillysmiles76]

understood

[@prashantdubey4112]

understood

[@javierdavidhernandezestrad7334]

understood

[@manideepdeepnaidugorle7308]

understood

[@shaiksoofi3741]

understood

[@studybits1604]

us