Show problems as
Classic problem #3006MediumTwo PointersStringBinary SearchRolling HashString MatchingHash FunctionZ AlgorithmKnuth–Morris–Pratt AlgorithmBoyer–Moore String-Search Algorithm

Find Beautiful Indices in the Given Array I

Real-world version: Nearby Marker Positions
Tracked in this browser only
Read Find Beautiful Indices in the Given Array I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A transcript is the lowercase string s. You are also given two lowercase marker words a and b, and a reach k.

A position i is flagged when both of the following hold:

  • a appears in the transcript starting at position i, meaning s[i .. i + a.length - 1] equals a;
  • there is some position j where b appears in the transcript, meaning s[j .. j + b.length - 1] equals b, whose distance from i satisfies abs(i - j) <= k.

The positions i and j may be equal and the two markers are allowed to overlap, and a and b may be the same word. Return every flagged position, sorted from smallest to largest. Return an empty list when no position is flagged.

Examples

Example 1

Input
s = "abcabc", a = "abc", b = "bc", k = 1
Output
[0, 3]

`a` starts at positions 0 and 3. Marker `b` starts at position 1, one away from 0, and at position 4, one away from 3, so both positions are flagged.

Example 2

Input
s = "axxxb", a = "a", b = "b", k = 3
Output
[]

`a` starts only at position 0 and `b` starts only at position 4. The distance is 4, which is more than the reach of 3, so nothing is flagged.

Example 3

Input
s = "bqqqa", a = "a", b = "b", k = 4
Output
[4]

`a` starts at position 4 and `b` starts at position 0. The distance is 4, which the reach allows, and a `b` before an `a` counts just the same.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def beautiful_indices(s: str, a: str, b: str, k: int) -> list[int]:
Java
public List<Integer> beautifulIndices(String s, String a, String b, int k)

More on the same topics