Find Pattern Starts with a Nearby Second Pattern
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find Pattern Starts with a Nearby Second Pattern
You are given a 0-indexed string `s`, strings `a` and `b`, and an integer `k`.
Return every index `i` satisfying both conditions:
- The complete string `a` occurs in `s` starting at `i`, so `0 <= i <= s.length - a.length`.
- There is at least one index `j` where the complete string `b` occurs in `s`, with `0 <= j <= s.length - b.length` and `|j - i| <= k`.
Return the qualifying indices in increasing order. The distance is between the starting indices of the two occurrences.
### Examples
**Example 1**
```text
Input: s = "ababa", a = "aba", b = "ba", k = 1
Output: [0,2]
```
String `a` starts at indices `0` and `2`; string `b` starts at `1` and `3`. Each start of `a` has a start of `b` at distance one. The two occurrences of `a` overlap, which is allowed.
**Example 2**
```text
Input: s = "catxxcatxxdog", a = "cat", b = "dog", k = 5
Output: [5]
```
String `a` starts at `0` and `5`, and `b` starts at `10`. The start at `5` qualifies because its distance from `10` is exactly five. The start at `0` does not qualify.
### Constraints
- `1 <= k <= s.length <= 10^5`.
- `1 <= a.length, b.length <= 10`.
- `s`, `a`, and `b` contain only lowercase English letters.
### Clarifying Questions
- Can occurrences overlap? Yes; the conditions impose no non-overlap requirement.
- Can `i` and `j` be equal? Yes, if both patterns occur there. In particular, this can happen when `a == b`.
- Can the same occurrence of `b` support several returned indices? Yes; occurrences are not consumed.
- Does one qualifying `i` appear repeatedly if several `j` values are nearby? No; return that index once.
- What if a pattern is longer than `s`, or `b` never occurs? No matching start exists for that pattern, so the result is empty.
### C++ Interface
```cpp
class Solution {
public:
vector<int> beautifulIndices(string s, string a, string b, int k) {
}
};
```
### Reasoning Checkpoints
- Check complete pattern occurrences and the inclusive distance between their starting indices.
- Return every qualifying index exactly once in increasing order, including overlapping occurrences.
- Justify correctness and resource use for the full stated string-length bound.
```hint Use the order of occurrence positions
Find all starting positions of b in increasing order. As you visit starting positions of a from left to right, consider which b positions could lie between i - k and i + k. A b position already below the lower limit will remain too small for later i values.
```
Overview: Find every occurrence of one pattern with a nearby second-pattern start, preserving overlaps, inclusive distance, sorted output and the full input bounds.