Shortest Way to Form String

For business inquiries email [e-mail] 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

[@KevinNaughtonJr]

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

[@Archcorsair]

Yes.

[@KevinNaughtonJr]

Daniel S ok so it’s not just me

[@surendra9935]

We are with you too dude

[@KevinNaughtonJr]

Surendra hahaha

[@saumya1singh]

@@KevinNaughtonJr KZbin showing "You can not donate in this country or region?" 🤔

[@anandprakash4995]

You are Awesome ! Crystal clear explanation !! learnt a lot !!

[@KevinNaughtonJr]

Anytime and happy to hear that thanks :)

[@Mai_Bharatwaasi]

Thanks a lot Kevin!! you are doing great :)

[@idemchenko-js]

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!

[@rmadhavmca1]

thanks for adding videos frequently. I really appreciate it.

[@RafaelBritodeOliveira]

me too

[@KevinNaughtonJr]

you got it

[@KevinNaughtonJr]

@@RafaelBritodeOliveira anytime!

[@bdc225]

Good stuff again man 🤝

[@KevinNaughtonJr]

thanks

[@casual_chess]

Thank you for these videos sir❤

[@KevinNaughtonJr]

Anytime thanks for the support

[@prakad97]

Nice.. appreciate the regular uploads man..!!

[@KevinNaughtonJr]

you got it!

[@faraz7409]

my man! thanks for the vid very helpful!

[@KevinNaughtonJr]

anytime Faraz thanks for the support!

[@somasishsahoo]

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

[@ShaliniNegi24]

Such an elegant solution it is! Thanks for the videos

[@KevinNaughtonJr]

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!

[@ShaliniNegi24]

@@KevinNaughtonJr sir, Surely I will try.

[@KevinNaughtonJr]

Shalini Negi amazing can’t wait to see you join :)

[@VilliSopuli]

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.

[@jaatharsh]

awesome well explained, thanks buddy

[@ChocolateMilkCultLeader]

so when you do charAt(i++) it first evals charAt(i) and then increments i?

[@KevinNaughtonJr]

devansh yep!

[@TheRaviraaja]

will binary search on target string will help in reducing time complexity. O(nm) is very high

[@raviashwin1157]

what was that song played at the beginning of the video?

[@renetchi]

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

[@divyanshukr]

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

[@vaibs1001]

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

[@tusharmarda295]

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.

[@KevinNaughtonJr]

Nice!

[@jkrw3540]

good, I had the same solution in my mind, BTW, how to do that if this time we can concatenate substrings and not subsequences?

[@sabisyed]

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

[@raviapiit]

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. :)

[@dipteshsil9299]

Was wondering if we need the subsequence string. We can avoid that. That way we will be able to improve efficiency.

[@KevinNaughtonJr]

I think we need it cuz otherwise how do we remember what character we're gonna take on each iteration?

[@dipteshsil9299]

@@KevinNaughtonJr we can simply use the j variable. not reset to 0. line 5 reset to while( j < target.length() )

[@jasminegeorge1149]

@@KevinNaughtonJr Here is the code without using subsequence, we can keep track using only j while(j

[@ozgurgonen9061]

yup, just uses the length() method, so an int "len" would be enough

[@kumarc4853]

looks like this can have constant space by using a counter rather than a builder. TThank you for the video.

[@AshokBathini]

@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

[@renetchi]

Maybe need to store array of array for spos since the source length can be 0-1000

[@lazzuuu21]

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(?)

[@JSDev776]

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?

[@surendra9935]

Thank you Kevin. I pinged you in instagram to make a motivational video. love 💙 you and your videos. Take Care 😃

[@KevinNaughtonJr]

thanks for reaching out!

[@aliara1568]

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)

[@charan775]

wow thanks for the video. but these are premium questions right? you uploading them isn't a problem?

[@godismygeneral]

Hey Kevin what is the runtime of this algo?

[@utalmighty]

Probably O(nm) n length of source m length of target

[@vaishali874]

can we use a subsequence more than once?

[@kumarc4853]

yes

[@surepasu]

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'

[@Brodskyb523]

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

[@zn4798]

Brute force TLE!

[@shriharikulkarni3986]

TC is O(mn), not accepted in interview.. Can you please post O( n log m ) explanation

[@abhinavgupta750]

Can source have character duplication?

[@chrisy.703]

excellent greedy method

[@ShivamGupta-dm7kf]

I want your song playlist pls

[@sharkk2979]

How u come up with a solution? I am binge watching ur videos.

[@sureshchaudhari4465]

with due respects sir why i am stuck while forming logics for such questions kindly help

[@zhakaske5671]

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.

[@Brodskyb523]

That's wrong. It should be 3: "ad" + "c" + "b"

[@scnullois]

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.

[@vk1618]

Check alternate soln

[@rahulshrivastava3040]

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.

[@gnanyreddy3030]

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

[@harsha2s2udupa]

I think this would fail if the source string is "abcabcd" and target is "abcd" .

[@ShaliniNegi24]

I was also thinking of this test case :/

[@ShaliniNegi24]

For even this case also source: "dfed" target: "fed"

[@-harshayadav]

@@ShaliniNegi24 why will it fail? i guess it works perfeclty fine

[@krishnamohansharma8859]

Put the code on your github. It's nowhere to be found

[@pratikchowdhury9210]

Lol that 1 dislike wonder why

[@KevinNaughtonJr]

it was me

[@wian7284]

@@KevinNaughtonJr 😂😂😂 You dint seriously say that! GENIUS!!

[@KevinNaughtonJr]

wian haha I’m jk