1163. Last Substring in Lexicographical Order

Problem Link

Description

---

Given a string s, return the last substring of s in lexicographical order.

 

Example 1:

Input: s = "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: s = "leetcode"
Output: "tcode"

 

Constraints:

• 1 <= s.length <= 4 * 105
• s contains only lowercase English letters.

Solution

---

Python3

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i, indexes = 0, list(range(n))
        
        while len(indexes) > 1:
            new = []
            mx = max([s[i + j] for j in indexes if i + j < len(s)])
 
            for k, j in enumerate(indexes):
                if k - 1 >= 0 and indexes[k - 1] + i == j:
                    continue
                if i + j >= len(s):
                    break
                if s[i + j] == mx:
                    new.append(j)
            i += 1
            indexes = new
            
        return s[indexes[0]:]