<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>

from collections import deque

class Solution:
    
    # get ord from 1 -> 27
    def ord_1(self, c):
        return ord(c) - 96
    
    def hash_string(self, string, p_powers, m, p):
        hash_ = 0
        for i, char in enumerate(string):
            if i not in p_powers:
                p_powers[i] = p_powers[i-1] * p % m
            hash_ = (hash_ + self.ord_1(char) * p_powers[i]) % m 
        return hash_
 
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        p = 31
        m = 196613

        len_s, len_a, len_b = len(s), len(a), len(b)

        if len_b > len_s or len_a > len_s:
            return []

        p_powers = {0: 1}
        a_hash, b_hash = self.hash_string(a, p_powers, m, p), self.hash_string(b, p_powers, m, p)
        beautiful_indices = []
        a_q = deque()
        latest_b = - 1
        rolling_hash = [0] * (len_s + 1)
        for i, char in enumerate(s):
            # update our rolling hash
            if i not in p_powers:
                p_powers[i] = p_powers[i-1] * p % m

            rolling_hash[i+1] = (rolling_hash[i] + self.ord_1(char) * p_powers[i]) % m

            # check for a
            if i >= (len_a - 1):
                curr_hash = (rolling_hash[i + 1] - rolling_hash[i + 1 - len_a] + m) % m
                a_hash_comparison = a_hash * p_powers[i+1-len_a] % m
                if curr_hash == a_hash_comparison:
                    if latest_b != -1 and abs(latest_b - i - 1 + len_a) <= k:
                        beautiful_indices.append(i+1-len_a)
                    else:
                        a_q.append(i+1-len_a)

            # check for b
            if i >= (len_b - 1):
                curr_hash = (rolling_hash[i + 1] - rolling_hash[i + 1 - len_b] + m) % m
                b_hash_comparison = b_hash * p_powers[i+1-len_b] % m
                if curr_hash == b_hash_comparison:
                    latest_b = i+1-len_b
                    while a_q:
                        a_item = a_q.popleft()
                        if abs(a_item - latest_b) <= k:
                            beautiful_indices.append(a_item)

        return beautiful_indices

       
1699