0623MediumTwo PointersStringBinary SearchRolling HashString MatchingHash FunctionZ AlgorithmKnuth–Morris–Pratt AlgorithmBoyer–Moore String-Search Algorithm

Nearby Marker Positions

Tracked in this browser only

Write code

Trains the technique from

LeetCode 3006Find Beautiful Indices in the Given Array I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n * (|a| + |b|)) to locate every marker occurrence, plus O(n) for the single forward walk.Space O(n) for the two lists of occurrence positions and the answer.

First gather the start positions where `a` appears and the start positions where `b` appears. Scanning the transcript and comparing a window of the right width at each offset produces both lists already in ascending order. Because both lists ascend, the second one can be walked with a single pointer that only ever moves forward: for the position of `a` in hand, advance the pointer past every `b` position that lies more than the reach behind, then the position the pointer now rests on is the smallest `b` position not too far behind, so one comparison against the far end of the reach settles the question. Positions are appended in increasing order, which is the order the answer needs.

Pythonentry point: beautiful_indices

def beautiful_indices(s, a, b, k):
    # O(n * (|a| + |b|)) time, O(n) space. Collect the start positions of both
    # markers in ascending order, then walk the first list once while a single
    # pointer moves forward through the second, dropping every second-marker
    # position that has fallen more than k behind. Because both lists ascend,
    # the pointer never has to move backwards, so the front of the surviving
    # window is the closest candidate at or after the current position.
    n = len(s)
    len_a = len(a)
    len_b = len(b)
    starts_a = [i for i in range(n - len_a + 1) if s[i:i + len_a] == a]
    starts_b = [j for j in range(n - len_b + 1) if s[j:j + len_b] == b]
    answer = []
    pos = 0
    for i in starts_a:
        while pos < len(starts_b) and starts_b[pos] < i - k:
            pos += 1
        if pos < len(starts_b) and starts_b[pos] <= i + k:
            answer.append(i)
    return answer

The obvious version

For every position where `a` appears, look at each position within the reach on either side and test directly whether `b` starts there. Keep the position as soon as one such test succeeds.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_beautiful_indices(s, a, b, k):
    n = len(s)
    answer = []
    for i in range(n - len(a) + 1):
        if s[i:i + len(a)] != a:
            continue
        low = i - k
        if low < 0:
            low = 0
        high = i + k
        found = False
        for j in range(low, high + 1):
            if j + len(b) <= n and s[j:j + len(b)] == b:
                found = True
                break
        if found:
            answer.append(i)
    return answer

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in