LeetCode-in-Java

3006. Find Beautiful Indices in the Given Array I

Medium

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 <= 105
• 1 <= a.length, b.length <= 10
• s, a, and b contain only lowercase English letters.

Solution

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("java:S6541")
public class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int q) {
        char[] sc = s.toCharArray();
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        int[] lpsa = getLps(ac);
        int[] lpsb = getLps(bc);
        int mo;
        int[] comp = new int[sc.length];
        int[] st = new int[sc.length];
        int si = 0;
        int k;
        mo = -bc.length + 1;
        if (bc[0] == sc[0]) {
            comp[0] = 1;
            if (bc.length == 1) {
                st[si++] = mo;
            }
        }
        for (int i = 1; i < comp.length; i++) {
            mo++;
            if (sc[i] == bc[0]) {
                comp[i] = 1;
            }
            k = comp[i - 1];
            if (k == bc.length) {
                k = lpsb[k - 1];
            }
            while (k > 0) {
                if (bc[k] == sc[i]) {
                    comp[i] = k + 1;
                    break;
                }
                k = lpsb[k - 1];
            }
            if (comp[i] == bc.length) {
                st[si++] = mo;
            }
        }
        int sia = 0;
        mo = -ac.length + 1;
        List<Integer> ret = new ArrayList<>();
        if (si == 0) {
            return ret;
        }
        if (sc[0] == ac[0]) {
            comp[0] = 1;
            if (ac.length == 1 && st[0] <= q) {
                ret.add(0);
            }
        } else {
            comp[0] = 0;
        }
        for (int i = 1; i < comp.length; i++) {
            mo++;
            if (sc[i] == ac[0]) {
                comp[i] = 1;
            } else {
                comp[i] = 0;
            }
            k = comp[i - 1];
            if (k == ac.length) {
                k = lpsa[k - 1];
            }
            while (k > 0) {
                if (ac[k] == sc[i]) {
                    comp[i] = k + 1;
                    break;
                }
                k = lpsa[k - 1];
            }
            if (comp[i] == ac.length) {
                while (sia < si && st[sia] + q < mo) {
                    sia++;
                }
                if (sia == si) {
                    break;
                }
                if (mo >= st[sia] - q && mo <= st[sia] + q) {
                    ret.add(mo);
                }
            }
        }
        return ret;
    }

    private int[] getLps(char[] xc) {
        int[] r = new int[xc.length];
        int k;
        for (int i = 1; i < xc.length; i++) {
            if (xc[i] == xc[0]) {
                r[i] = 1;
            }
            k = r[i - 1];
            while (k > 0) {
                if (xc[k] == xc[i]) {
                    r[i] = k + 1;
                    break;
                }
                k = r[k - 1];
            }
        }
        return r;
    }
}

This site is open source. Improve this page.