Maximum Length of a Concatenated String with Unique Characters
Vložit
- čas přidán 8. 07. 2024
- For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Instagram: / kevinnaughtonjr
Twitter: / kevinnaughtonjr
Patreon: / kevinnaughtonjr
Merch: teespring.com/stores/kevin-na...
GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
look at me. by ☽shinji☾
/ balm - Věda a technologie
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
patreon: www.patreon.com/KevinNaughtonJr
merch: teespring.com/stores/kevin-naughton-jrs-store
I have a doubt. When you call the maxUnique function recursively inside that function for the first time..the current doesnt change only index changes. It means the current is always an empty string right. So what is the use of it. Why do we have to do this for empty string.
@@stonecoldcold2941 At first i also have the same thought. then i wrote all the recursive calls ..that first recursion call plays a big role when the 2nd recursive call happens .
What i most like in your videos is just the fact how you explain things kind of complicated in a easy way... i feel like i can finally understand things in the same way i feel a overwhelming will for learn more and more.. thanks for sharing your knowledge. Big hug from Brazil
Thanks so much really appreciate that
wouldn't it be much faster converting all to a set - if it's size is longer than the initial one - throw it our right away - otherwise do it with all permutations?
10:05 We loop through the original array (left to right), and at each step we simulate concatenating the item we’re on to our string or not concatenating it (skipping it)
Excellent explanation!
The complexity can be improved if you don't make those two calls always but based on condition. If characters from the array[index] are already present in current, then calling backtrack function with the next index and same Current string would be the case and otherwise call the backtrack function would be with the next index and Current + array[index].
You are doing a great work
SLIGHT HICCUP ! only strings that have unique characters can be added so before adding a string check if it has unique characters itself and with the string already formed . this way at an average 50 % recursive calls would be saved
I'm confused, isn't it a worse issue than that? By adding strings that don't have unique characters, isn't he allowing for incorrect solutions (strings that are longer and have redundant characters). Why wouldn't his algorithm just give you the concatenation of all of the strings in the array? Maybe I'm missing something in the code, but I don't see where it's excluding invalid concatenations.
@@BrettClimb it doesnt. It will always run at worst case runtime, but it will only take the answer if it is unique. In a real interview they may ask if there's better ways to cut down the number of strings you are checking
Bro complexity 📈📈📈🥵
Are you saying this is 2^n runtime? If yes, is it not too slow? Can you tell whether I understood right?
Hi Kevin! Thanks for the explanation. I really like your videos. Stay safe.
Thanks Nikita! If you like my explanations be sure to join the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining a premium plan if you can!
nice video! thank you for explaining the recursive solution. Could you elaborate more on why we need the first recursive call? I didn't get that part
So to create all possible substring, we have two oprions fpr each string in the given vector either to include it or ignore it. First recursive call ignores string at index and second recursive call includes the string at the given index.
Can we use a Hash Map of currently added words by their unique chars instead of current string?
This way you will check, do we do one (a char in not in the hash map) or two (a char is in the hash map, thus replace or don't replace it) recursive calls not iterratng through current. Thanks!
Dmitry Karpenko I believe we need to use the entire string from each array string .. so HashMap, we won’t be able to track each string in an array individually.
Hey are you solving premium leetcode questions in your playlists of specific companies?
Shouldn't the helper function being considered when calculating the time complexity?
I think the time complexity should be O(w*2^n) where w is the average length of words and n is the number of words
Yep
Thank you for highlighting this.
Hey Kevin! Question - I don't think you recall why we need to simulate both the recursive calls, whats the purpose of not adding to current?
["abc", "de", "def"] shows why you need to simulate not adding to current.
u doing a great job inspiring us all,although u explain really well but its me ex who made me realise my inner potential and dream of working in product based company.cheers.
thanks!
Hey Kevin (or anyone really). Do you think questions are reasonable to expect for SWE internship positions as well? I know its still good to practice but just wanted to judge the difficulty level. Thanks!
Jaspreet S depends on the question in my opinion. If you need help with questions be sure to sign up for the interviewing service I created it’ll teach you how to solve all kinds of problems like this thedailybyte.dev/?ref=kevin I recommend joining the premium tier if you can
Hi kevin why we are storing result in an array instead of an integer
He answered it in the comments "The reason for using the integer array instead of an integer is because integers are passed by value (not reference like an integer array) so therefore it doesn't retain it's value throughout all the recursive calls"
I tried to use an integer to keep track of the maximum length, and the output is 0. Can you tell me why it doesn't work? (I used for exact code besides the result array)
hey John sorry I meant to touch on that and forgot to in the problem. The reason for using the integer array instead of an integer is because integers are passed by value (not reference like an integer array) so therefore it doesn't retain it's value throughout all the recursive calls
Thank you very much Kevin!
John Smith anytime!
@@KevinNaughtonJrAh, this actually clarified a lot of things for me :) Thanks!
@@waterislife9 Anytime! If this helped you, you should definitely check out thedailybyte.dev/ :)
Kevin ! why dont we use an int variable instead of using int array of a unit size ?
Well, one way of doing would be creating a private static int property, so you could access this property from any of this class's methods instead of passing it as an input.
To create a variable that is passed by reference. An integer passed in the same way would be passed by value and could not be mutated.
IMO it's a pretty ugly way to do it, but it works.
At 1:29, would the string un+ue be considered a concatenation?
Nah the u is the acharacter, hence not valid
Can you please explain why you used an array of size 1 instead of maintaining a single integer variable?
because he wants to modify it every time he found a new max length, so if he tried to modify a global integer he will get an error, instead with a global array it will work ! you can try it .
May I ask why you decided to use an integer array of one item over a single integer variable?
Because in Java, primitives are passed by value. So when you try to update an int, it won’t update the original variable but its copy. An array value on the other hand is it’s address. So in some ways it’s passed by reference. Please note that java is pass by value only
This is a dynamic programming question, not a "Classical DFS" as mentioned at 3:39. It can be solved either through tabulation or memoization. The solution presented here is sub-optimal because it duplicates a significant amount of work.
Kevin, great explanation. Thanks!
I'd suggest to improve time complexity by:
1. don't call recursion if the string already has duplications;
2. use memoization inside uniqueCharCount function.
Improve the space complexity a little bit by using 4byte int instead of array of 26 integers:
int length = 0;
int binaryRepresentation = 0;
for (char c : current.toCharArray()) {
int shift = 1;
shift
I would say you don't understand what complexity is :)
@@z08840 actually, it sounds like you don't
@@DanKaschel actually nobody cares how it sounds to you.
@@z08840 yes indeed 😂
I am not able to do a dry run of this code, can anyone help?
why if (counts[ c - 'a']++ > 0) instead of > 1 ? I'm thinking the first encounter of each character++ is valid right? after that then > 1 means repeated?
counts array represents how many duplicates.
i.e.
a b -> we have 0 duplicate for a. so count[ch - 'a'] == 0
if aab -> we have 1 duplicate for a. so count[ch - 'a'] == 1
so if count[ch - 'a']++ > 0 means we have as least 1 duplicates.
count array is used to count how many extra / duplicate chars, but not used to count how many characters encountered.
hope it helps you.
He's using post increment, first it'll get compute then added by 1
At first I thought how the hell am I gonna do this , then I looked at the constraints and I was like brute force😒😒😒
lmfao
So what is like a good indicator of 'Use DFS or BFS on this problem?' Like where exactly do you use DFS in this problem?
Usually in problems where you need to produce all possible combinations of something, you'll need to use DFS. Example problems in addition to this one are combinations, permutations, and subsets
Just be vary of the fact that dfs is expensive. So try to implement caching whereever possible
I don’t think he explained the reason for two recursive call .. he just read the code. Any one else(perhaps who thanked for the video) can explain here
A little lost on the time and space complexity here. You said in the video that the space complexity is the same as the time. But you're saying time is O(2^N) and space is O(N)? Isn't space supposed to be O(2^N) as well?
Thanks in advance,
Eugene
nice background mate :)
thanks mate :)
Can we concatenate all the elements together in the given list and then delete same elements within concatenated string thus giving us the longest unique string?
Nice explanation, please try to explain time complexity in more detail.
Can we just calculate the length of the max and the second max length string
And return the the sum of them?
the hint in the leet code says use DP, so i thought there will be a sophisticated DP solution, but this is simple recursion.
wow wow
thanks for making video
all lots of love from India
Abhay Tiwari anytime
For this solution, is the result array being passed by value? That's the only this makes sense. I thought Java was a pass by reference language?
result array is being passed by reference. passed by reference allows the callee function (maxUnique) to return the reference to the result array after it's value has been modified.
@@leanobajio he isn't returning anything though
@@ChocolateMilkCultLeader he is passing the result array to maxUnique and then returning the 0th element in it in the maxLength function
I think the pointer is being passed here. That's why he might have taken array instead of variable.
Hey Kevin,
Would it be more efficient to only call the backtrack function with the concatenation if the current string + concatenated string only contained unique characters and move that unique character check? That way you would only be doing a partial depth-first-traversal instead of a full depth-first traversal.
Thanks for your videos!
By allowing strings to be concatenated that share a character, isn't he allowing for incorrect solutions? Why wouldn't his algorithm just give you the concatenation of all of the strings in the array? Maybe I'm missing something in the code, but I don't see where it's excluding invalid concatenations.
@@BrettClimb if they share a character the helper returns -1 which will never be > than anything
Why is result an array? Couldn't it be an integer?
Thanks for the video. This approach will work for getting maximum unique characters in concatenated strings, but it has re-evaluated same strings in the take it / not take it decision tree. How about looping through the string array, concatenate strings along the way and recurse? Like:
public void LongestUniqueStringRecursive(string[] s, int index, string current, int []max)
{
if (current.Length > max && CheckUniqueness(current))
{
max[0] = Math.Max(max[0], current.Length);
}
for (int i = index; i< s.Length; i++)
{
LongestUniqueStringRecursive(s, i + 1, current + s[i], max);
}
}
This code generates and evaluates string once.
However, if the question is changed to "Tell me how many ways to generate strings with unique characters from the given array, Kevin's solution is simplest if the code is altered to return int (representing a find)
I think the time complexity is going to be too large( n^n), If I'm not wrong 🤔
I solved it using DP by applying the technique of Longest Increasing Subsequence. But I was only able to pass 82 / 85 test cases. Can anyone let me know what am I doing wrong?
import collections
def hasUniqueChars(ss):
c = collections.Counter(ss)
for x in c.values():
if x > 1:
return False
return True
def lenOfConcatenatedSubstringWithUniqueChars(arr):
dp = [x if hasUniqueChars(x) else '' for x in arr]
dpCopy = dp[:]
print(dp)
for i in range(len(dp)):
if dp[i] == '':
continue
for j in range(i):
p = dpCopy[j]+dp[i]
if hasUniqueChars(p) and len(p) > len(dpCopy[i]):
dpCopy[i] = p
maxLen = 0
for s in dpCopy:
maxLen = max(maxLen, len(s))
return maxLen
Why does result have to be an array? Why can't it be just an integer? And if it is an integer, how can we make it so that the recursive function modifies the actual integer result instead of a copy?
arrays in java are stored in heap memory thus preserved during recursive stack calls.
Nice
"hella confusing... [""un"" ""iq"",""ue""] especially with those void returns can you go into one simple case provided...we make all the calls down ? We make four calls to the function and get to the end of the array, it runs and then returns true back into third call 'ue' okay result is still blank, that returns TRUE to the previous recursive call, and then again for the second recursive call. What is being modified here other than result? I basically don't get the back propagation here, can you work out the first backpropagation case or two? why would you NOT take current ? Because it is NOT unique?"
We can use memorization to reduce time complexity as this problem has repeated sub problems.
Not Gonna Lie, I think DFS is gonna save my F-ing life LMAO
Oh yeah! Classical DFS, I knew tennis was the answer for this problem.
Are this the interview question in all microsoft position?
Likely no this is just one of the most asked question for microsoft technical interviews at the time.
Pretty easy i believe if you understand recursion :) btw nice video
thanks
You have been lifting a lot in lockdown it seems xD
Had the constraint been *1
Hey Kevin! there is a special reason that you are preferred to solve the problems with Java and not with Python? I know both but not professional with none of them. I'm trying to understand which will be better for me. thanks!
If you have the choice and don't feel more comfortable with either one I def suggest python, I just use Java because I'm the most comfortable with it and used it the most but I think python is definitely better to interview with generally speaking
@@KevinNaughtonJr thanks for your quick response! can i ask you why do you think that?
@@shanigitelman8625 it's a faster and more forgiving language
was anyone else able to do this with just two for loops?
Do you work there?
I think that there is a sexy dp aproach for this problem
agreed!
One of the types of dfs #review
You are not passing the interview with that time complexity!
Space complexity is on point though
public int uniqueCharCount(String s) {
int uniqueChars = (int) s.chars().distinct().count();
return s.length() == uniqueChars ? uniqueChars : -1;
}
niiice
LIS with unique chars condition
Hi Kevin, big fan of yours. Just a small mistake I would like to point out. counts【c-'a'】++ > 1 should be the check instead of >0 because we are trying to find duplicates here !
why int[] result instead of just int result ??
because result in dfs recursion should be deep copied. You can use int[] result OR use int result BUT put it out of function signature as global value.
i.e.
public class {
int result = 0;
public funcA() {
}
}
I still don’t get it :(
Alex Hong is this because int would just be passed by value and therefore not modified by the recursive calls? If that’s the case, would passing an Integer object instead of int achieve the same things?
could you do the bitmanipulation technique. it is better solution
meaning a bit mask?
@@KevinNaughtonJr yes. Idk wat bit mask is
Why recursion keep going when string already have duplicated characters，should returned i think
Aren't invalid concatenations of strings being performed given your constraints? For example, "abc" + "cde" gives "abccde" which has a longer unique character count, but isn't valid. I don't see where you are filtering out these solutions.
Nice camera
thanks
n +iq + ue => nique is an unique string right? Why it is not considered
It must be a whole word "un"...not a single character 'n' from the word '"un"
Since we are calling the function again and again, couldn't we have memoized?
definitely, memoizing would help limit the runtime to be bounded by the number of unique subproblems you'd just have to determine how you wanna represent your state (probably the index you're at and the string you currently have)
Can't we solve it by generating all the substrings. Which only takes o(n2) time complexity.
Generating all substrings is O(2^n) not "n2"
Damn u look swole Kevin 👍😂
hahah thanks
Using an array of size 1 to avoid global variables is really smart.
Why should we avoid global variables?
@@shashu1999 it's considered a code smell to use a global variable to store a state that only applies to a specific method invocation. Imagine if the method was called again; the global variable would still have the old length.
You look good 👌🏾
Impresssed by your coding ease.
thanks!
Can u tell a better optimised approach
Hey Kevin,
Are you alright ? I see different background in your videos recently, I hope virus is not bothering you.
I’m safe don’t worry just had to get out of NYC with all the craziness going on thanks for asking hoping you’re safe too!
Can you do a DFS version of this?
did not understand char [c-'a']++ thing
It is to get array position of a given character while looping over the string. for example the ASCII value of 'a' is 65 and if you get character as 'a' , c-'a' = 0 will give position of a..thereby getting the count of unique characters.
deepak jain thanks for explaining :)
@@deepakjain-dr7ds thanks Mate!
I didn't understand anything. You were just writing the solution, maybe it's just me tho
This answer seems inefficient. You can optimize the string concatenation/comparison and cut down on complexity,
Please use dark mode my eyes hurts
if you do this in the interview, I gurantee that you will fail.
your on mac microsoft is beating apple🤣
I love your content kevin, but you keeping the camera away from yourself to show off your shoulders and Biceps is not acceptable at all. Sincerely, Arpit.
what?????
@@KevinNaughtonJr JK dude, I love you.
😂😂😂
This just made me hate java more than ever