Longest common substring problem suffix array part 2

Longest common substring problem suffix array part 2

Related Videos:
Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs
Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI
Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw
Longest common substring 1/2: https://www.youtube.com/watch?v=Ic80xQFWevc
Longest common substring 2/2: https://www.youtube.com/watch?v=DTLjHSToxmo
Longest repeated substring: https://www.youtube.com/watch?v=OptoHwC3D-Y

Data structures repository:

Kattis problem:

My website:
Developer tools I used in the creation/testing of the content in these videos:

1) Sublime text, my favorite lightweight code editor (https://www.sublimetext.com).
NOTE: I’m often asked about the color scheme I use, find it here: https://github.com/williamfiset/dotfiles/tree/master/sublime

2) Kite, a free AI-powered coding assistant that provides smart code completions while typing:

Get Kite



  1. bharatha teja on October 15, 2021 at 8:54 am


  2. Nitesh Garg on October 15, 2021 at 8:59 am

    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.

  3. doomlord271 on October 15, 2021 at 9:10 am

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

  4. Rushil Patel on October 15, 2021 at 9:10 am

    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 ?

  5. Shaw Ankush on October 15, 2021 at 9:12 am

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

  6. Sigi on October 15, 2021 at 9:13 am

    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?

  7. subhadip panja on October 15, 2021 at 9:14 am

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

  8. Hiren Chauhan on October 15, 2021 at 9:16 am

    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?

  9. rohit bohra on October 15, 2021 at 9:20 am

    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.

  10. Bruh on October 15, 2021 at 9:47 am

    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?

  11. Squirrelschaser on October 15, 2021 at 9:47 am

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

  12. Sasank Tadepalli on October 15, 2021 at 9:47 am

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