<p>The hash of a <strong>0-indexed</strong> string <code>s</code> of length <code>k</code>, given integers <code>p</code> and <code>m</code>, is computed using the following function:</p>

<ul>
	<li><code>hash(s, p, m) = (val(s[0]) * p<sup>0</sup> + val(s[1]) * p<sup>1</sup> + ... + val(s[k-1]) * p<sup>k-1</sup>) mod m</code>.</li>
</ul>

<p>Where <code>val(s[i])</code> represents the index of <code>s[i]</code> in the alphabet from <code>val(&#39;a&#39;) = 1</code> to <code>val(&#39;z&#39;) = 26</code>.</p>

<p>You are given a string <code>s</code> and the integers <code>power</code>, <code>modulo</code>, <code>k</code>, and <code>hashValue.</code> Return <code>sub</code>,<em> the <strong>first</strong> <strong>substring</strong> of </em><code>s</code><em> of length </em><code>k</code><em> such that </em><code>hash(sub, power, modulo) == hashValue</code>.</p>

<p>The test cases will be generated such that an answer always <strong>exists</strong>.</p>

<p>A <b>substring</b> is a contiguous non-empty sequence of characters within a string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, power = 7, modulo = 20, k = 2, hashValue = 0
<strong>Output:</strong> &quot;ee&quot;
<strong>Explanation:</strong> The hash of &quot;ee&quot; can be computed to be hash(&quot;ee&quot;, 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. 
&quot;ee&quot; is the first substring of length 2 with hashValue 0. Hence, we return &quot;ee&quot;.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;fbxzaad&quot;, power = 31, modulo = 100, k = 3, hashValue = 32
<strong>Output:</strong> &quot;fbx&quot;
<strong>Explanation:</strong> The hash of &quot;fbx&quot; can be computed to be hash(&quot;fbx&quot;, 31, 100) = (6 * 1 + 2 * 31 + 24 * 31<sup>2</sup>) mod 100 = 23132 mod 100 = 32. 
The hash of &quot;bxz&quot; can be computed to be hash(&quot;bxz&quot;, 31, 100) = (2 * 1 + 24 * 31 + 26 * 31<sup>2</sup>) mod 100 = 25732 mod 100 = 32. 
&quot;fbx&quot; is the first substring of length 3 with hashValue 32. Hence, we return &quot;fbx&quot;.
Note that &quot;bxz&quot; also has a hash of 32 but it appears later than &quot;fbx&quot;.
</pre>

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

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= power, modulo &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= hashValue &lt; modulo</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
	<li>The test cases are generated such that an answer always <strong>exists</strong>.</li>
</ul>

class Solution:
  def subStrHash(self, s: str, p: int, m: int, k: int, hashValue: int) -> str:
    s = ''.join(reversed(s))

    def val(c):
      return ord(c) - ord('a') + 1

    pk = p**k

    class RollingHash(SlidingWindow.Observer):
      def __init__(self):
        self.value = 0

      def enter_cell(self, ri):
        self.value = (self.value * p + val(s[ri])) % m

      def exit_cell(self, li):
        self.value = (self.value - val(s[li]) * pk) % m


    result = ''
    rolling_hash = RollingHash()
    for li, ri in LengthBoundSlidingWindow(s, k, k, rolling_hash).run():
      if rolling_hash.value == hashValue:
        result = ''.join(reversed(s[li:ri + 1]))

    return result


from collections.abc import Sequence


class SlidingWindow:
  """Represents a sliding window algorithm framework.

  This class provides a structure for implementing sliding window algorithms.
  Concrete implementations should inherit from this class and override the
  should_contract_left() and is_window_good() methods.
  """

  class Observer:

    def init(self, sequence: Sequence):
      self.seq = sequence

    def start_run(self, _range):
      ...

    def finish_run(self):
      ...

    def enter_cell(self, right_idx: int):
      ...

    def exit_cell(self, left_idx: int):
      ...

  def __init__(self, sequence: Sequence, observer=None):
    self.seq = sequence
    self.observer = observer if observer is not None else self.Observer()
    self.observer.init(sequence)

  def should_contract_left(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def is_window_good(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def run(self, _range=None):
    _range = _range if _range is not None else range(len(self.seq))
    self.observer.start_run(_range)
    li = _range.start
    for ri in _range:
      self.observer.enter_cell(ri)
      while li <= ri and self.should_contract_left(li, ri):
        step = self.observer.exit_cell(li)
        li += step if step else _range.step
      if li <= ri and self.is_window_good(li, ri):
        yield li, ri
    self.observer.finish_run()


class LengthBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_len: int, max_len: int, observer=None):
    super().__init__(sequence, observer)
    self.min_len = min_len
    self.max_len = max_len

  def should_contract_left(self, li: int, ri: int) -> bool:
    return ri - li + 1 > self.max_len

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_len <= ri - li + 1 <= self.max_len


class AggregateBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_value, max_value, observer=None):
    super().__init__(sequence, observer)
    self.min_value = min_value
    self.max_value = max_value

  def should_contract_left(self, li: int, ri: int) -> bool:
    return self.observer.aggregate() > self.max_value

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_value <= self.observer.aggregate() <= self.max_value


class Count(SlidingWindow.Observer):

  def start_run(self, _range):
    from collections import Counter
    self.counter = Counter()

  def enter_cell(self, ri):
    self.counter[self.seq[ri]] += 1

  def exit_cell(self, li):
    val = self.seq[li]
    self.counter[val] -= 1
    if self.counter[val] == 0:
      del self.counter[val]


class Min(SlidingWindow.Observer):

  def start_run(self, _range):
    from collections import deque
    self._queue = deque()

  def enter_cell(self, ri: int):
    while self._queue and self.seq[self._queue[-1]] > self.seq[ri]:
      self._queue.pop()
    self._queue.append(ri)

  def exit_cell(self, li: int):
    while self._queue and self._queue[0] <= li:
      self._queue.popleft()

  def min(self):
    return self.seq[self.min_idx()]

  def min_idx(self):
    assert self._queue
    return self._queue[0]


class Sum(SlidingWindow.Observer):

  def start_run(self, _range):
    self.sum = 0

  def enter_cell(self, ri: int):
    self.sum += self.seq[ri]

  def exit_cell(self, li: int):
    self.sum -= self.seq[li]

  def aggregate(self):
    return self.sum 
18000