Shortest Way to Form String
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
----------------------------------------------------------------------------------------------------------------
xo bored llif3 by young frontwood
/ xo-bored-lif3 - Věda a technologie
IS IT JUST ME OR DO I LITERALLY LOOK LIKE A GIANT SITTING AT THIS DESK???
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
merch: teespring.com/stores/kevin-naughton-jrs-store
patreon: www.patreon.com/KevinNaughtonJr
Yes.
Daniel S ok so it’s not just me
We are with you too dude
Surendra hahaha
@@KevinNaughtonJr CZcams showing "You can not donate in this country or region?" 🤔
thanks for adding videos frequently. I really appreciate it.
me too
you got it
@@RafaelBritodeOliveira anytime!
Thanks a lot Kevin!! you are doing great :)
You are Awesome ! Crystal clear explanation !! learnt a lot !!
Anytime and happy to hear that thanks :)
Hey Kevin, you've listened to your audience, no candles this time :) people were getting nervous :) Thanks for your videos, you're doing a great good!
Good stuff again man 🤝
thanks
Thank you for these videos sir❤
Anytime thanks for the support
Such an elegant solution it is!
Thanks for the videos
Shalini Negi anytime! If you like my explanations be sure to sign up for the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining a premium tier if you can!
@@KevinNaughtonJr sir, Surely I will try.
Shalini Negi amazing can’t wait to see you join :)
Nice.. appreciate the regular uploads man..!!
you got it!
Do you think it would work / be any faster to have a Hashmap mapping all the characters in the source mapping to a list of integers (indices they appear at)? So they idea would be that instead of always looping thru the whole source string char by char, just looping through the occurrences of the chars and forming the subsequence starting from those indices and calculating their length and then comparing and using the longest subsequence and then moving on to the next remaining. I wasn't able to see this problem since I'm not a premium anymore.
so when you do charAt(i++) it first evals charAt(i) and then increments i?
devansh yep!
awesome well explained, thanks buddy
what was that song played at the beginning of the video?
my man! thanks for the vid very helpful!
anytime Faraz thanks for the support!
Hi Kevin,
Appreciate all your efforts in making these videos. Have cleared a lot of my doubts.
Regarding this algo. I can say that one of the case is missing.
Inner while loop has to be broken if char are mismatch.
Example - Source - "pabc" , Target - "abcpbc" - O/P - 3 but above program o/p is 2
a break statement will resolve this.
Thanks
Som
looks like this can have constant space by using a counter rather than a builder. TThank you for the video.
will binary search on target string will help in reducing time complexity. O(nm) is very high
def shortestWay(source: str, target: str) -> int:
res = 0
i = 0
while i < len(target):
exists = False
for j in range(len(source)):
if i < len(target) and source[j] == target[i]:
exists = True
i +=1
if not exists:
return -1
res +=1
return res
source = "xyz"
target = "xzyxz"
shortestWay(source, target)
can be done in linear time. Create a map of char to integer of source. Then check target's character appear in map and do not update your counter as long as character of target string is always appearing at > prevIndex +1 .
private int formString(String source, String target) {
if(source.isEmpty()) {
return -1;
}
Map charMap = new HashMap();
for(int i = 0; i < source.length(); i++) {
charMap.put(source.charAt(i), i);
}
int count = 0;
int countSubString = 0;
int index = -1;
boolean MultiCharacterSubsequenceBeingBuilt = false;
int lengthOfSubSequence = 1;
for(int i = 0; i < target.length(); i++) {
if(charMap.get(target.charAt(i)) == null) {
return -1;
}
int mapIndex = charMap.get(target.charAt(i));
count++;
if(index == -1) {
index = mapIndex;
} else if(index > mapIndex -1) {
index = mapIndex;
MultiCharacterSubsequenceBeingBuilt = false;
count = count - (lengthOfSubSequence - 1);
lengthOfSubSequence = 1;
}
else if(index 1) {
count = count - (lengthOfSubSequence - 1);
}
return count;
}
Hey Kevin, can we also do this in O(m log n) time? I am thinking we can keep a sorted list of positions of each char in source( O(n) time and O(n) space, preprocessing). Then for each char in target, we just have to find the same char's next greater position in source (greater than the index we found in source for the previous char of target). Since each char's index list is sorted, this can be done in log n time. Therefore, m chars in target and for each char log n search time = O (m log n).
Thought of the same, here is the code for it :
int shortestWay(string source, string target) {
int sourceLen = source.length();
int targetLen = target.length();
vector srcCharPos(26, vector());
int minSub = 1;
for (int i = 0; i < sourceLen; ++i) {
srcCharPos[source[i] - 'a'].push_back(i);
}
int prevCharIndex = -1, j = 0;
while (j < targetLen) {
int charIndex = target[j] - 'a';
auto it = std::upper_bound(srcCharPos[charIndex].begin(), srcCharPos[charIndex].end(), prevCharIndex);
int index = it - srcCharPos[charIndex].begin();
if (index >= srcCharPos[charIndex].size()) {
if (prevCharIndex == -1)
return -1;
minSub++;
prevCharIndex = -1;
} else {
prevCharIndex = srcCharPos[charIndex][index];
++j;
}
}
return minSub;
}
I think, we don't need StringBuilder, because that was just being used for retrieving subsequence length. This will improve overall performance IMHO. Btw, great work. :)
How about storing the source as hashmap and then looping all target, if current target is in source hashmap then continue to next target. If current target location in source is smaller than prev one then add the total count
Worst case time complexity can be improved to O(sourcelength + targetlength * log(sourcelength)), though not required for such small input sizes.
First you create a map from char in source to a sorted array of indices in source where that char occurs. This will take one scan of source. Then, while forming substrings, you can directly use binary search on the array of the character you are trying to insert into the substring.
Nice!
good, I had the same solution in my mind, BTW, how to do that if this time we can concatenate substrings and not subsequences?
so this is basically the greedy approach, match the longest sequence possible and repeat, but can there be a situation where you need to stop before matching further down and match from start again?
excellent greedy method
@All-
How about this? I felt this is easier to understand. Do u see any bugs in this code?
T: O(target.length + source.length)
S: O(1) = space for 26 ints to store indexes of all characters.
Note: assumes no duplicates in source string.
public static int countSubsequences(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0)
return 0;
//maintain indexes of all characters of source
int[] spos = new int[26];
for (int i = 0; i < s.length(); i++) {
spos[s.charAt(i) - 'a'] = i;
}
int prevPos = -1;
int count = 0;
for (int i = 0; i < t.length(); i++) {
int pos = spos[t.charAt(i) - 'a'];
//if the current character in target is out of sequence, then it's a fresh beginning of another sequence.
if(pos
Maybe need to store array of array for spos since the source length can be 0-1000
What if the source contains a same character? like "aab" and the target is "aaa"? the answer would be 2, but your answer will return 3(?)
Was wondering if we need the subsequence string. We can avoid that. That way we will be able to improve efficiency.
I think we need it cuz otherwise how do we remember what character we're gonna take on each iteration?
@@KevinNaughtonJr we can simply use the j variable. not reset to 0. line 5 reset to while( j < target.length() )
@@KevinNaughtonJr Here is the code without using subsequence, we can keep track using only j
while(j
yup, just uses the length() method, so an int "len" would be enough
Thank you Kevin. I pinged you in instagram to make a motivational video. love 💙 you and your videos. Take Care 😃
thanks for reaching out!
Hey Kevin what is the runtime of this algo?
Probably O(nm)
n length of source
m length of target
TC is O(mn), not accepted in interview.. Can you please post O( n log m ) explanation
can we use a subsequence more than once?
yes
Brute force TLE!
I think the solution not working for below test cases..please correct me if I am wrong
For this scenario it should return -1 , but returning 2
# sourcestr = 'abc'
# targetstr = 'abcbc1'
For this scenario it should return 3
, but returning 2...
sourcestr = 'adbcklm'
targetstr = 'aklmbc'
For your first test case, the problem states that "Both the source and target strings consist of only lowercase English letters from 'a'-'z'." So, your input should not contain the number "1".
For your second test case, it should in fact return 2, not 3. This is because of the following: "aklm" + "bc". On the first pass, you can take "aklm" because they are in that order in the source, and then when you have to check the source a second time, you get the "bc".
Can source have character duplication?
with due respects sir why i am stuck while forming logics for such questions kindly help
same idea efficient implementation
int shortestWay(string source, string target) {
int m = source.size();
int n = target.size();
int i=0, j=0;
bool found = false;
int res = 0;
while (j
It doesn't work for s="abcd" and t="adcb", answer must be 4, and not 3, you need to adjust the inner loop to break when there is mimatch.
That's wrong. It should be 3:
"ad" + "c" + "b"
wow thanks for the video. but these are premium questions right? you uploading them isn't a problem?
This is decent approach but you can probably do better by factoring out the section that finds the largest subseq into a dynamic programming problem which memoizes the sub-problems.
How u come up with a solution? I am binge watching ur videos.
I think this would fail if the source string is "abcabcd" and target is "abcd" .
I was also thinking of this test case :/
For even this case also
source: "dfed"
target: "fed"
@@ShaliniNegi24 why will it fail? i guess it works perfeclty fine
Kevin, Is there a lot of value in going through your videos or any tech interview videos, knowing that current situation will halt all hiring. Do not get me wrong, your videos are fantastic.
Check alternate soln
Put the code on your github. It's nowhere to be found
Lol that 1 dislike wonder why
it was me
@@KevinNaughtonJr
😂😂😂
You dint seriously say that! GENIUS!!
wian haha I’m jk