Anchor Near a Companion

Medium

You are given a string text, two short strings anchor and companion, and an integer reach. A position i (0-based) counts if anchor starts at i in text and there is also an occurrence of companion in text starting at some position j with |i - j| ≤ reach. Occurrences may overlap each other, and anchor and companion may be the same string. Return all such positions in increasing order.

Example 1

text="catdogxxxxcat", anchor="cat", companion="dog", reach=3 → [0]

"cat" starts at positions 0 and 10, "dog" starts at position 3. For position 0 the distance is 3 ≤ 3; for position 10 it is 7, which is too far.

Example 2

text="aaaa", anchor="aa", companion="aaa", reach=1 → [0, 1, 2]

"aa" starts at 0, 1 and 2, and "aaa" starts at 0 and 1. Every start of "aa" is within 1 of some start of "aaa".

Example 3

text="abcde", anchor="e", companion="z", reach=5 → []

Constraints

1 ≤ reach ≤ len(text) ≤ 10⁵
1 ≤ len(anchor), len(companion) ≤ 10
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String Binary Search String Matching Hash Function Rolling Hash

Similar problems

Word Near an Anchor Hard Target From Word Beginnings Medium Suffixes Echoing the Start Hard Phrase From Word Beginnings, Long Edition Hard Longest Piece Seen Twice Medium

Input

text="catdogxxxxcat", anchor="cat", companion="dog", reach=3

Expected

[0]

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.