<p>Given a string <code>s</code>, return <em>the last substring of</em> <code>s</code> <em>in lexicographical order</em>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abab&quot;
<strong>Output:</strong> &quot;bab&quot;
<strong>Explanation:</strong> The substrings are [&quot;a&quot;, &quot;ab&quot;, &quot;aba&quot;, &quot;abab&quot;, &quot;b&quot;, &quot;ba&quot;, &quot;bab&quot;]. The lexicographically maximum substring is &quot;bab&quot;.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;
<strong>Output:</strong> &quot;tcode&quot;
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>5</sup></code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution:

    def char_to_int(self, ch: str) -> int:
            return ord(ch) - ord('a') +  1

    def hash_seq(self, s: str) -> List[int]:
        mod = 1000000007
        base = 29
        f = []
        pow = []
        for i, ch in enumerate(s):
            if i == 0:
                f.append(self.char_to_int(ch))
                pow.append(1)
            else:
                f.append(int((f[-1] * base + self.char_to_int(ch)) % mod))
                pow.append(int(pow[-1] * base % mod))
        return f, pow

    def lastSubstring(self, s: str) -> str:
        hash_seq, pow = self.hash_seq(s)
        max_value = 0
        candidates = []
        for i, ch in enumerate(s):
            max_value = max(self.char_to_int(ch), max_value)
        for i, ch in enumerate(s):
            v = self.char_to_int(ch)
            if v == max_value:
                candidates.append(i)
        ii = self.find_last_sub_str(s, hash_seq, pow, candidates)
        return  s[ii:]

    def cal_hash_subseq(
        self,
        hash_seq: List[int],
        pow: List[int],
        start: int,
        end: int,    
    ):
        mod = 1000000007
        if start > 0:
            return int((hash_seq[end] + mod - hash_seq[start - 1] * pow[end - start + 1] % mod) % mod)
        else:
            return hash_seq[end]

    def find_last_sub_str(
        self,
        s: str,
        hash_seq: List[int],
        pow: List[int],
        candidates: List[int],    
    ) -> int:
        def compare(start1: int, start2: int) -> bool:
            # Find the longest common prefix
            le =  0
            ri = len(s) - start2 - 1
            common = 0
            while le <= ri:
                mid = int((le + ri) / 2)
                h1 = self.cal_hash_subseq(
                    hash_seq,
                    pow,
                    start1,
                    start1 + mid, 
                )
                h2 = self.cal_hash_subseq(
                    hash_seq,
                    pow,
                    start2,
                    start2 + mid
                )
                if start1 == 0  and start2 == 199994:
                    print(f'{le} - {ri} | {h1} - {h2}')
                if abs(h1 - h2) < 2 and s[start1 + mid] == s[start2 + mid]:
                    le = mid + 1
                    common = mid 
                else:
                    ri = mid - 1
            if common == len(s) - start2 - 1:
                return True
            return self.char_to_int(s[start1 + common + 1]) > self.char_to_int(s[start2 + common + 1])
            
        ll = 0
        rr = len(candidates) - 1
        while ll < rr:
            if compare(candidates[ll], candidates[rr]):
                rr -= 1
            else:
                ll += 1
        return candidates[ll]
6454