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

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

Рет қаралды 69,645

2 жыл бұрын

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

Пікірлер: 127

@takeUforward 2 жыл бұрын

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

@shreyanshmittal9381 11 ай бұрын

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

@_-6912 2 жыл бұрын

understood and its clever way of implementation.

@vidhishah9154 2 жыл бұрын

Understood, Thanks for making hard things easy.

@lavanyam3224 3 ай бұрын

Brilliant approach!

@wolfrikz7238 2 жыл бұрын

understood, great explanation ❤️

@ashishsachan08 2 жыл бұрын

Great...Thanks..

@UECAshutoshKumar 3 ай бұрын

Thank you 🙏

@jolly_dollyyy 2 жыл бұрын

understood!!

@rushidesai2836 Күн бұрын

Thanks Striver!

@techdemy4050 2 жыл бұрын

@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 2 жыл бұрын

Same query

@thinkingmad1685 2 жыл бұрын

Use map then worst case will be nlogn

@nishankdeep3084 Жыл бұрын

understood bhaiya thank you bhaiya

@sivaganesh4489 2 жыл бұрын

Thanks dude

@utkarsh_108 2 жыл бұрын

understooooood. thanks bhaiya 🙂

@devendrapatil07 2 жыл бұрын

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

@manoharmanu9240 Жыл бұрын

Understood 🙌

@abhayj8706 2 жыл бұрын

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

@yogendrajhala4147 2 жыл бұрын

Bro check aditya dp series, it will help u

@Rohitkumar-ks9io 2 жыл бұрын

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

@aakashparmar560 2 жыл бұрын

Understood!!!

@satyampande684 2 жыл бұрын

Understood!!

@meghamaheshwari4445 2 жыл бұрын

Understood!

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

@bhai-bm4kj Жыл бұрын

Understood bhaiya

@hemantvardani1436 Жыл бұрын

Thanks

@satyampande684 2 жыл бұрын

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 2 жыл бұрын

Hashing

@sarthak7438 2 жыл бұрын

I'm not getting tle with trie approach

@satyampande684 2 жыл бұрын

@@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 2 жыл бұрын

understood😁

@bhai-bm4kj Жыл бұрын

Love you sir

@arihantjammar8888 8 ай бұрын

Understood 😊

@AmandeepSingh-uq3wp 2 жыл бұрын

understood

@chandrachurmukherjeejucse5816 11 ай бұрын

Understood.

@sohamsen7892 2 жыл бұрын

Understood

@mohitsingh7793 Жыл бұрын

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

@arahul6098 Жыл бұрын

understood..

@your_name96 Жыл бұрын

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

@coderhat1980 2 жыл бұрын

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.

@addityasharma6426 Жыл бұрын

understood :-)

@anujtyagi4047 2 жыл бұрын

use unordered set instead of set

@tukaighosh4383 2 жыл бұрын

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 2 жыл бұрын

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

@adolft_official Жыл бұрын

To insert a string of length L, it will take O(L) time for insertion in hashmap

@ar3568row 9 ай бұрын

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

@tanujsharma2874 2 жыл бұрын

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

@Harsh-pv7pb Жыл бұрын

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

@satwiktatikonda764 8 ай бұрын

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

@Yash-uk8ib 2 жыл бұрын

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 2 жыл бұрын

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)

@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 4 ай бұрын

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

@sanjuchandra9405 3 ай бұрын

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

@sagarbora7768 2 жыл бұрын

same content i learned in masterclass

@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 2 жыл бұрын

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

@Agent47_live Жыл бұрын

what teaching app are you using?

@anshulgoel1940 10 ай бұрын

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

@GyaneshTiwari-dw4zb Жыл бұрын

understood ++

@vanshchaudhary8291 11 ай бұрын

@champion5946 2 жыл бұрын

UnderStood

@souravchakraborty9777 2 жыл бұрын

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

@Sandeepg255 2 жыл бұрын

via suffix array

@shivampathak1371 2 жыл бұрын

In code, line 4

@yogeshvaishnav7856 2 жыл бұрын

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

@takeUforward 2 жыл бұрын

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

@yogeshvaishnav7856 2 жыл бұрын

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

@takeUforward 2 жыл бұрын

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

@amborishnath7755 2 жыл бұрын

@akashsahu2571 4 ай бұрын

cfbr

@LowkeyCoder 6 ай бұрын

"Understood"

@AlokYadav-SKB Жыл бұрын

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

@shradhaydham4745 3 ай бұрын

why don't we need trie class here?

@rahulsrivastava9710 2 жыл бұрын

Time limit exceeded... ???

@mkat21 8 ай бұрын

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

@user-tj3us8il6f 2 жыл бұрын

**********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 2 жыл бұрын

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

@visheshagrawal8676 3 ай бұрын

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