<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]:
        # we can do this in several parts
        # 1) find all indices that satisfy i
        ## use two pointer, with constant window size a
        ## move one at a time, including a char and not including a char
        ## we can keep track of chars in the window using a hashmap
        ## whenever the characters are the same, we can compare the strings
        # 2) find all indices that satisfy j
        ## same as 1)
        # 3) iterate through the indices that satisfy both, and return the ones that have difference less than k
        ## use n^2 algo
        
        
        # 1) find i
        def find_candidates(a):
            i_map = defaultdict(int)
            a_map = defaultdict(int)
            i_candidates = []
            l = 0
            r = l
            while r < len(a):
                i_map[s[r]]+=1
                a_map[a[r]]+=1
                r+=1
                
            if i_map == a_map:
                if s[l:r] == a:
                    i_candidates.append(l)

            while r < len(s):
                i_map[s[r]]+=1
                i_map[s[l]]-=1
                if i_map[s[l]] == 0:
                    i_map.pop(s[l])
                l+=1

                if i_map == a_map:
                    if s[l:r+1] == a:
                        i_candidates.append(l)
                r+=1
            return i_candidates
        
        if len(s) < len(a) or len(s) < len(b):
            return []
        i_candidates = find_candidates(a)
        j_candidates = find_candidates(b)
        
        # determine if they are valid
        ret = set()
        for i in i_candidates:
            for j in j_candidates:
                if abs(i-j) <= k:
                    ret.add(i)
                    break
        
        ret = list(ret)
        ret.sort()
        
        return ret
            
2147