<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 lastSubstring(self, word: str) -> str:
        if len(word) == 1:
            return word
        
        ordering = [(ord(char), ord(char)) for char in word]
        curr_len: int = 1
        while True:
            all_vals: List[int] = sorted(list(set(ordering)))
            val_to_rank: Dict[int, int] = {val: rank + 1 for rank, val in enumerate(all_vals)}
            ordering = [val_to_rank[val] for val in ordering]

            # Check if maximum value is unique.
            if ordering.count(max(ordering)) == 1:
                break
            
            new_ordering: List[int] = []
            for idx, order in enumerate(ordering):
                snd_half_start_idx = idx + curr_len
                snd_half_order = 0 if snd_half_start_idx >= len(ordering) else ordering[snd_half_start_idx]
                new_ordering.append(
                    (order, snd_half_order)
                )
            curr_len *= 2
            ordering = new_ordering
        
        max_index: int = ordering.index(max(ordering))
        return word[max_index:]

1740