You are given strings s, a, and b, along with an integer k.

An index i is called beautiful if both conditions hold:

1. The substring of s starting at i matches a, meaning s[i..i + len(a) - 1] == a.

2. There exists an index j such that the substring of s starting at j matches b, meaning s[j..j + len(b) - 1] == b, and the distance between the starting indices satisfies |i - j| <= k.

Return all beautiful indices i in increasing order.

Constraints:

• $1 \leq$ k $\leq$ s.length $\leq 5 \cdot 10^5$

• $1 \leq$ a.length, b.length $\leq 5 \cdot 10^5$

• s, a, and b contain only lowercase English letters.

Input: s = "abcdeabcdf"-str, a = "abc"-str, b = "bcd"-str, k = 1-int
Output: [0, 5]-List[int]
Explanation: a = "abc" occurs at indices 0 and 5, and b = "bcd" occurs at indices 1 and 6. For i = 0, j = 1 gives |0 - 1| = 1 <= k, and for i = 5, j = 6 gives |5 - 6| = 1 <= k, so both are beautiful.

Input: s = "aaaaaa"-str, a = "aa"-str, b = "aa"-str, k = 0-int
Output: [0, 1, 2, 3, 4]-List[int]
Explanation: a and b both occur at indices 0 through 4 (length-2 substrings). With k = 0, we need j = i exactly, and since b starts at every index where a starts, all those indices are beautiful.

Input: s = "ababa"-str, a = "aba"-str, b = "bab"-str, k = 1-int
Output: [0, 2]-List[int]
Explanation: a = "aba" occurs at indices 0 and 2 (overlapping matches), and b = "bab" occurs at index 1. Both |0 - 1| = 1 and |2 - 1| = 1 are within k, so both indices are beautiful.

Input: s = "xyzabcxyz"-str, a = "abc"-str, b = "xyz"-str, k = 2-int
Output: []-List[int]
Explanation: a = "abc" occurs at index 3, and b = "xyz" occurs at indices 0 and 6. The distances |3 - 0| = 3 and |3 - 6| = 3 are both greater than k, so index 3 is not beautiful.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.