Understanding
3 experiences · Other (3)
3 entries
Understanding the intuition behind prevLPS = lps[prevLPS - 1] in LPS array computation
Understanding your strengths is one thing, but translating them in an interview is another.
Understanding Leetcode Questions
Understanding the intuition behind prevLPS = lps[prevLPS - 1] in LPS array computation
Interview Experience
https://preview.redd.it/8697el6vw7rg1.png?width=924&format=png&auto=webp&s=b73d1eca7ebba78295bc462ce0205d851eda38a8 I understand what the LPS (Longest Prefix Suffix) array does, but I’m confused about the intuition behind the update step when a mismatch occurs: prevLPS = lps[prevLPS - 1] I know this avoids going back character by character, but I don’t fully get: 1. Why this works : how does jumping to lps[prevLPS - 1] guarantee we still check all valid possibilities? 2. Why it doesn’t skip a valid prefix that could match the current character. 3. How it manages to land at the correct “next best prefix length” without missing anything. Can someone break down the reasoning behind this step? A small example showing why the jump works would be really helpful. And what exactly are we jumping back to??? Thanks :)