Google Coding Interview Question - Longest String Chain

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming #CodingInterview

[IsaacAsante]

Gotta love those coding interview questions! Keep it up, Kamil!

[HimanshuSingh-rczy]

Straight question, no bullshit and this is our Errichto

[genctasbasi]

Fun starts at 18:35, for those interested. The beginning of the video is also massively helpful. I've been checking several LC submissions with no luck, finally got the point with this video. Great stuff, thanks.

[learnfromarandomguy]

You're a great teacher. The part by part breakdown was very good. I appreciate your hard work.

[utsavpopli]

I could not stop myself but to comment here. Well explained !! loved the overall approach, starting from basics and taking it all the way to lower the complexity
Thanks for awesome video !

[GeorgeHFonseca]

Great video! I find it amazing the way you explain how to improve the complexity of a solution

[techwithwhiteboard]

i am simple nigga

i see a polish competitive programmer( erichto )

i like it

have pressed subscribe countless but even number of times

🙂

[sevak.harutyunyan]

Thanks man. It's very hard these times to find a great content of algorithmic coding. Keep it up man!

[Paradise-kvfn]

Very helpful!i had solved this problem before but i didnt consider removing the characters instead of adding them...thus i had an AL*2 helper function instead of L^2 ike yours wanted to see and learn how your thought process works...i too will now start analysing the problem from right to left...i have solved a lot of problems which were solved in reverse order but I guess that i still usually miss analysing from that angle...

[ayushbhatnagar]

Great video with awesome explanation. Looking forward to more videos like these. Thanks a lot

[devdeejay]

Hey bro! You are very calm composed and knowledgable! You seem like a really nice person! Thank you so much for putting in efforts to get us this content. Really thankful! And wish you a great success ahead :)

[dcts]

I think you can find out if you can go from wordOne to wordTwo in O(L) time with this approach (please correct me if im wrong):
- init two pointers for both words at index 0
- iterate over each char of the longer word (increase pointer of second word every iteration)
- increase pointer of word1 ONLY IF both characters match
- after the whole loop, check: pointer1===(pointer2-1) => valid transition, otherwise not.

[dascoolst]

If L is large and A is small, a non-deterministic solution would be to compute hashes with some large prime mod.

[jimmorrisshen]

For this problem, I found that python code is very short.
```
class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = {}
for word in sorted(words, key=len):
dp[word] = max(dp.get(word[:i]+word[i+1:], 0)+1 for i in range(len(word)))
return max(dp.values())

```
I tried to translate to C++. Essentially, it has the same idea. I feel that during the interview, especially for the black board coding, the code length sometimes also matters. I put the code here for reference.
```
class Solution {
public:
int words) {
unordered_map<string, int> dp;
for(auto &word:words) dp[word] = 1;
sort(words.begin(), words.end(), [](string &a, string &b){
return a.length()<b.length();
});
for(auto &word:words){
for(int j=0; j < (int) word.length(); ++j){
string new_word = word.substr(0, j)+word.substr(j+1);
= max(dp[word], dp[new_word]+1);
}
}
int res = 0;
for(auto& d:dp)res=max(res, d.second);
return res;
}
};

```
The complexity of above code is sorting O(NlogN) + two layer for loops and new_word generation is O(NLL). Runtime of C++ is 64 ms.
Hope it helps.

[abhinav_]

Very elaborate explanation, really expands your understanding about the topic👌
Thanks😊

[NavneetVermalivefree]

great way of explaining things.. please keep making these kind of videos

[navneethingankar]

I have already solved the problem, but not in a optimised way, you are really good. while preparing for interviews i found optimising the solution is more difficult than just solving the problem.this is the kind of stuff i am looking for, Thank you for that.Could you also cover 2 pointer category which is the most asked category i noticed, like leetcode 1248, 1234, 1004, 930, 992.i found that people solve very uniquely and optimised way, that i have never seen before, if possible please make a video on this category.Thanks in advance.

[vasujain]

Excellent explanation Kamil! This really cleared my concepts

[harshitgupta]

sheesh came in my placement test yesterday wasn't able to do that though, great video anyways thanx!

[ramram]

Please create an course on algorithms and competitive programming from basics it's helps many like me