Longest common substring problem suffix array part 2

[@shawankush4575]

These are clear and on point. Loved them. Thanks for making these.

[@niteshgarg464]

Great video. So i was trying to implement it and use it in question on Kattis. But not clear what sentinels i can use when n can be up to 100. As i would always have to start from 35 and end at 97. I thought i could maybe start using doubles after that like ## but i feel this will add lot of complexity like maintaining index range for sentinels instead of just index. Any simpler approaches which can tackle this easily.

[@WilliamFiset-videos]

Hi Nitesh, I suggest you convert your alphabet and sentinel values into numbers rather than characters and shift the scale to make the sentinel values always less than your alphabet

[@niteshgarg464]

@@WilliamFiset-videos Thanks. But Slightly confused now suppose i convert my chars to 1-26 so i can easily add sentinels like -1, -2 and all. If now all this is inside string then what would be the diff between 12 - ab and 12 - l. This could work if i break the string into array and then do this of course. Actually if i break it into a array like convert abcd. to ['a', 'b', 'c', 'd'] then whenever i run out of sentinels i can double or triple them as well. Is this what you meant ? After converting to numbers you cannot keep it in string right it will have to be in an array.

[@rohitbohra4248]

Hey William! Thank you for all your videos. Your content is awesome. Here I am having trouble in getting the intuition behind solving the LCS problem by this method? Can you tell more on why this works better? How's is the time complexity linear( O(n1+n2+...nm) from prev video ) ? Sorting will take extra O(nlogn) where n is the sum of lengths + sentinels.

[@Squirrelschaser]

What a wild problem. You need a suffix array, LCP array, a hashmap, and finally apply sliding window minimum. Good luck to whoever gets asked this in an interview for k > 2 (else you would just use DP).

[@rahulsangvikar7973]

Even for k=2 this is better than DP, this is O(nlogn) (due to suffix array construction) whereas DP is O(n^2)

[@Squirrelschaser]

@@rahulsangvikar7973 Yes, I know, but you would never do this, if you k =2. Interviewer would most likely just want the DP solution.

[@Bruh-jw2ze]

Initially when u compared the two strings with LCP 0 & 2, Then why did u update the LCS Length. Coz as far I understood, you have to ignore any windows with 0 in them right?

[@doomlord271]

Great video! Could you make a video on how to create suffix and LCP array in O(n)?

[@WilliamFiset-videos]

Thank you for the suggestion! I'll need to do a bit more research on the construction algorithms if I decide to put together those videos.

[@sahilsingh1]

@@WilliamFiset-videos Did you make a video on it? If not can you suggest some easy to understand resources? My aim is to learn it only from coding competitions point of view, hence an algorithm which is easier to implement and understand would help me more than one which is convoluted and is a tiny bit faster.

[@sasanktadepalli1231]

Sir, do we have to take min LCP or max LCP?

[@subhadippanja3702]

Hi, Your videos are great. Can you please add a video explaining "Find the longest palindromic substring of a string using suffix array. e.g. abacdxzdcaba has aba as the longest palindrome,"

[@hirenchauhan3703]

Great Video. I love it. I've got one doubt. At 2:37 when window has two string 0 -> "BC#BCDC$BCDE%CDED&" and 2 -> "BCDC$BCDE%CDED&" if we apply range minimum query on it, we'll get answer 0 as minimum of (0, 2) = 0. So what should we take care of when we're implementing code?

[@WilliamFiset-videos]

Hi Hiren, because of how the LCP array is created we always omit the first entry in the window, so the minimum would be 2.

[@ibitedeadskunks]

@@WilliamFiset-videos I had the same question in my head, clarification on that would have been good because thats not clear at all

[@Sicaine]

What is the benefit of concatenating those 4 strings? I thought about it and don't get it. Is it just to make it easier to understand? Otherwise you probably could have created the suffix array from all 4 strings anyway right?

[@WilliamFiset-videos]

It's so that all four strings can be together when creating the suffix array (four individual suffix arrays wouldn't be nearly as useful). The goal is to find the LCS, and introducing sentinels allows comparing the four different strings together once the suffix array is built.

[@rushilp1230]

Do we have to take a max LCP or min LCP ? At 3:17 you have taken the largest LCP and before that you took lowest LCP , window {2,3} why did you not take 2 that time ?

[@talkingmango8658]

how do you figure out what "color" it is?

[@bharathateja2797]

thanks