<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;= 5 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= a.length, b.length &lt;= 5 * 10<sup>5</sup></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]:
        # Beautiful Indices:
        # - Start of 'a' substring within s
        # - Less than or equal to k distance from start of 'b' substring within s
        
        if len(a) > len(s) or len(b) > len(s): return []
        
        # s = "aaxyxyxyxyaaxyaaxyx", a = "x", b = "y", k = 8
        # i                *
        # j         *
        # ans = [2, 4, 6, 8]
        
        base, mod = 31, 10**9 + 7
        power_a, power_b = pow(base, len(a), mod), pow(base, len(b), mod)
        
        def char_to_int(c):
            return ord(c) - ord('a') + 1
        
        def remove_char(cur_hash, char, power):
            return (cur_hash - char_to_int(char) * power) % mod
        
        def add_char(cur_hash, char):
            return (cur_hash * base + char_to_int(char)) % mod
        
        def roll_hash(cur_hash, pointer, window, power):
            prev_char = s[pointer - 1]
            new_char = s[pointer + window - 1]
            return remove_char(add_char(cur_hash, new_char), prev_char, power)
        
        def get_hash(sub):
            h = 0
            for char in sub:
                h = add_char(h, char)
            return h
            
        target_a, target_b = get_hash(a), get_hash(b)
        
        left, right = 0, 0
        hash_a, hash_b = get_hash(s[:len(a)]), get_hash(s[:len(b)])
        ans = []
        
        def approx_equal(i, s2):
            return s[i] == s2[0] and s[i + len(s2) - 1] == s2[-1]
        
        while True:
            while hash_a != target_a:
                left += 1
                if left > len(s) - len(a): return ans
                hash_a = roll_hash(hash_a, left, len(a), power_a)
            
            while left - right > k or hash_b != target_b:
                right += 1
                if right > len(s) - len(b): return ans
                hash_b = roll_hash(hash_b, right, len(b), power_b)
            
            if hash_a == target_a and hash_b == target_b and abs(right - left) <= k:
                if approx_equal(left, a) and approx_equal(right, b):
                    ans.append(left)
            
            left += 1
            if left > len(s) - len(a): return ans
            hash_a = roll_hash(hash_a, left, len(a), power_a)
            
        return ans
1725