3008. Find Beautiful Indices in the Given Array II

Description

You are given a 0-indexed string s, a string a, a string b, and an integer k.

An index i is beautiful if:

• 0 <= i <= s.length - a.length
• s[i..(i + a.length - 1)] == a
• There exists an index j such that:
  • 0 <= j <= s.length - b.length
  • s[j..(j + b.length - 1)] == b
  • |j - i| <= k

Return the array that contains beautiful indices in sorted order from smallest to largest.

 

Example 1:

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

 

Constraints:

• 1 <= k <= s.length <= 5 * 105
• 1 <= a.length, b.length <= 5 * 105
• s, a, and b contain only lowercase English letters.

 

Solutions

Solution: Two Pointers

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @param {string} a
 * @param {string} b
 * @param {number} k
 * @return {number[]}
 */
const beautifulIndices = function (s, a, b, k) {
  const beautifulA = createKMP(s, a);
  const beautifulB = createKMP(s, b);
  const m = beautifulB.length;
  const result = [];
  let left = 0;

  for (const index of beautifulA) {
    while (left < m && beautifulB[left] - index < -k) {
      left += 1;
    }

    if (beautifulB[left] - index <= k) {
      result.push(index);
    }
  }

  return result;
};

function createKMP(s, target) {
  const n = s.length;
  const m = target.length;
  const lps = getLPS(target);
  const result = [];
  let a = 0;
  let b = 0;

  while (a < n) {
    if (s[a] === target[b]) {
      a += 1;
      b += 1;

      if (b === m) {
        result.push(a - m);
        b = lps[b - 1];
      }
    } else if (b > 0) {
      b = lps[b - 1];
    } else {
      a += 1;
    }
  }

  return result;
}

function getLPS(pattern) {
  const n = pattern.length;
  const lps = Array.from({ length: n }, () => 0);
  let left = 0;

  for (let index = 1; index < n; index++) {
    while (left && pattern[index] !== pattern[left]) {
      left = lps[left - 1];
    }

    if (pattern[index] === pattern[left]) {
      lps[index] = left + 1;
      left += 1;
    }
  }

  return lps;
}