Longest Happy Prefix - LPS table of KMP & Rolling Hash
Description Solution 1: LPS table from KMP Algorithm Use the lps table from the kmp algorithm. e.g: "ababab" lps = [0,0,1,2,3,4] lps[lps.length - 1] indicates the length of the longest prefix which is a suffix. Time Complexity: O(n) 117ms Space Complexity: O(n) 50.1MB var longestPrefix = function ( s ) { let n = s.length, lps = getLPS(s); let lastIdx = lps[lps.length - 1 ]; return s.slice( 0 , lastIdx); function getLPS ( str ) { let lps = Array (n).fill( 0 ); let i = 0 ; for ( let j = 1 ; j < n; j++) { while (i > 0 && str[i] !== str[j]) i = lps[i - 1 ]; // rollback if (str[i] === str[j]) { i++; lps[j] = i; } } return lps; } }; Solution 2: Rolling Hash Note: This solution does not handle collisions. Comparing the matching strings resulted in TLE. Create rolling hashes for the prefix and suffix. When the hashes match, record the largest index. Time Complexity: O(n) 126ms Space Complex...