Find Beautiful Indices in the Given Array II - KMP Algorithm [JS]
Description Solution: KMP Algorithm & Two Pointers Use a modified KMP algorithm to find all matches of a in s , and the same for b . Use two pointers to find the number of indices from a and b that are at most k distance apart. Anchor the pointer i going through indices from a . Move up the pointer j (for indices in b ) while greater than k distance before i . n = length of s , m = length of a and b Time Complexity: O(n + m) Space Complexity: O(m) var beautifulIndices = function ( s, a, b, k ) { let aIndices = kmp(s, a), bIndices = kmp(s, b); let ans = []; for ( let i = 0 , j = 0 ; i < aIndices.length && j < bIndices.length; i++) { while (j < bIndices.length && aIndices[i] - bIndices[j] > k) j++; if (j < bIndices.length && Math .abs(bIndices[j] - aIndices[i]) <= k) ans.push(aIndices[i...