LeetCode-in-Java

3008. Find Beautiful Indices in the Given Array II

Hard

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.

Solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        int[] lpsA = getLps(a);
        int[] lpsB = getLps(b);
        List<Integer> ans = new ArrayList<>();
        Deque<Integer> matchesA = new ArrayDeque<>();
        int n = s.length();
        int aLen = a.length();
        int bLen = b.length();
        int i = 0;
        int j = 0;
        while (i < n) {
            if (s.charAt(i) == a.charAt(j)) {
                i++;
                j++;
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = lpsA[j - 1];
                }
            }
            if (j == aLen) {
                int aStart = i - aLen;
                matchesA.offer(aStart);
                j = lpsA[aLen - 1];
            }
        }
        i = j = 0;
        while (i < n && !matchesA.isEmpty()) {
            if (s.charAt(i) == b.charAt(j)) {
                i++;
                j++;
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = lpsB[j - 1];
                }
            }
            if (j == bLen) {
                int bStart = i - bLen;
                j = lpsB[bLen - 1];

                while (!matchesA.isEmpty() && bStart - matchesA.peek() > k) {
                    matchesA.poll();
                }
                while (!matchesA.isEmpty() && Math.abs(matchesA.peek() - bStart) <= k) {
                    ans.add(matchesA.poll());
                }
            }
        }
        return ans;
    }

    private int[] getLps(String s) {
        int n = s.length();
        int[] lps = new int[n];
        int i = 1;
        int prevLps = 0;
        while (i < n) {
            if (s.charAt(i) == s.charAt(prevLps)) {
                prevLps++;
                lps[i++] = prevLps;
            } else {
                if (prevLps == 0) {
                    lps[i++] = 0;
                } else {
                    prevLps = lps[prevLps - 1];
                }
            }
        }
        return lps;
    }
}

This site is open source. Improve this page.