<p>You are given a <strong>0-indexed</strong> string <code>s</code>, a string <code>a</code>, a string <code>b</code>, and an integer <code>k</code>.</p>

<p>An index <code>i</code> is <strong>beautiful</strong> if:</p>

<ul>
	<li><code>0 &lt;= i &lt;= s.length - a.length</code></li>
	<li><code>s[i..(i + a.length - 1)] == a</code></li>
	<li>There exists an index <code>j</code> such that:
	<ul>
		<li><code>0 &lt;= j &lt;= s.length - b.length</code></li>
		<li><code>s[j..(j + b.length - 1)] == b</code></li>
		<li><code>|j - i| &lt;= k</code></li>
	</ul>
	</li>
</ul>

<p>Return <em>the array that contains beautiful indices in <strong>sorted order from smallest to largest</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;isawsquirrelnearmysquirrelhouseohmy&quot;, a = &quot;my&quot;, b = &quot;squirrel&quot;, k = 15
<strong>Output:</strong> [16,33]
<strong>Explanation:</strong> There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == &quot;my&quot; and there exists an index 4 with s[4..11] == &quot;squirrel&quot; and |16 - 4| &lt;= 15.
- The index 33 is beautiful as s[33..34] == &quot;my&quot; and there exists an index 18 with s[18..25] == &quot;squirrel&quot; and |33 - 18| &lt;= 15.
Thus we return [16,33] as the result.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcd&quot;, a = &quot;a&quot;, b = &quot;a&quot;, k = 4
<strong>Output:</strong> [0]
<strong>Explanation:</strong> There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == &quot;a&quot; and there exists an index 0 with s[0..0] == &quot;a&quot; and |0 - 0| &lt;= 4.
Thus we return [0] as the result.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= a.length, b.length &lt;= 10</code></li>
	<li><code>s</code>, <code>a</code>, and <code>b</code> contain only lowercase English letters.</li>
</ul>

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        """
        Notes
        -----
        TLDR - Find all substrings `a` and `b` in s. An index i is beautiful if it is the start of substring `a`, and a substring `b` starts within distance `k` of it.

        Step 1 - Find all substrings `a` in `s`.
        1. We have two choices at each index, either start checking if `a` starts here, or go to next index.
        2. So then we can check in a brute force manner. 
        3. 

        Step 2 - Find if there is a substring `b` starting `k` from each beautfil string.
        1. Way we do this is precomputing all the indexes b starts at. We store them in a list. When searching for `a`, we initially point to the first index in this list. 
           When the index `a` starts at surpasses the index in the bStart list, we increment the bStart list pointer. Then for each `a` we find we just check if the current or prev in the list
           is within distance k.
        2. We can do a little better on average by only checking if `a` is a substring 
        """
        bStartPos = _getBStartPosInS(s, b)
        currBStartPos = 0
        beautiful = []
        if bStartPos:
            for i in range(len(s)):
                if not _isFinalBStartPos(currBStartPos, bStartPos) and i >= bStartPos[currBStartPos+1]:
                    currBStartPos += 1
                nearestB = min(abs(i-bStartPos[currBStartPos]), abs(i-bStartPos[currBStartPos+1]) if not _isFinalBStartPos(currBStartPos, bStartPos) else float("inf"))
                if nearestB <= k:
                    if _startsAtIInS(s, i, a):
                        beautiful.append(i)
        return beautiful
        

def _getBStartPosInS(s: str, b: str) -> List[int]:
    bStartPos = []
    for i in range(len(s)):
        if _startsAtIInS(s, i, b):
            bStartPos.append(i)
    return bStartPos

def _startsAtIInS(s: str, s_i: int, b: str) -> bool:
    end = s_i+len(b)
    if end > len(s):
        matches = False
    else:
        matches = True
        for i in range(s_i, end):
            if s[i] != b[i-s_i]:
                matches = False
                break
    return matches

def _isFinalBStartPos(currBStartPos: int, bStartPos: List[str]) -> bool:
    return currBStartPos+1 == len(bStartPos)
466