Given a string s, return the last substring of s in lexicographical order.
 
Example 1:
Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:
Input: "leetcode"
Output: "tcode"

 
Note:

1 <= s.length <= 4 * 10^5
s contains only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def lastSubstring(self, s: str) -> str:
        

Solutions:
class Solution:
    def lastSubstring(self, s: str) -> str:
        #mx = \"\"
        #for i in range(len(s)):
        #    mx = max(mx,s[i:])
        #return mx
        index = {c: i for i, c in enumerate(sorted(set(s)))}
        cur, radix, max_val, max_i = 0, len(index), 0, 0
        for i in range(len(s)-1, -1, -1):
            cur = index[s[i]] + cur/radix
            if cur > max_val:
                max_val, max_i = cur, i
        return s[max_i:]

class Solution:       
    def lastSubstring(self, s: str) -> str:
        curr_value = 0
        max_value = 0
        max_idx = 0
        char_to_id = {c: i for i, c in enumerate(sorted(set(s)))}
        radix = len(char_to_id) ** (len(s) - 1)
        
        for i in range(len(s) - 1, -1, -1):
            curr_value = char_to_id[s[i]] + curr_value / len(char_to_id)
            # print(curr_value)

            if curr_value > max_value:
                max_value = curr_value
                max_idx = i

        return s[max_idx:]
        # index = {c: i for i, c in enumerate(sorted(set(s)))}
        # radix, val, cur, lo = len(index), 0, 0, 0
        # for i in range(len(s) - 1, -1, -1):
        #     cur = index[s[i]] + cur / radix
        #     print(cur)
        #     if cur >= val:
        #         lo, val = i, cur
        # return s[lo:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        # loop to find the max lexicographic  
        # substring in the substring array 
        # l = \"\" 
        # for i in range(len(s)-1,-1,-1): 
        #     l = max(l, s[i:]) 
        #     print(s[i:])
        # return l
       
        if len(set(s)) == 1:
            return s 
        idx = len(s) - 1
        for i in range(len(s)-2, -1, -1):
            k = 0
            while idx+k < len(s):
                cur, stored = ord(s[i+k]), ord(s[idx+k])
                if cur > stored:
                    idx = i
                    break
                elif cur < stored:
                    break
                k += 1
            if idx+k == len(s):
                idx = i
        return s[idx:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        # c = s[0]
        # for num in range(len(s)):
        #     if s[num] > c:
        #         i = num
        #         c = s[num]
        j = i + 1
        k = 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
            elif s[i+k] > s[j+k]:
                j += k + 1
                k = 0
            else:
                i = j
                j = i + 1
                k = 0
                
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i :]
        
        
        
#         maxchar = 'a'
#         index = []
        
#         for i in range(len(s)):
#             if s[i] > maxchar:
#                 maxchar = s[i]
#                 index.append(i)
#         # print(index)
#         maxstring = \"\"
        
#         for i in range(len(index)):
#             if s[index[i]:] > maxstring:
#                 maxstring = s[index[i]:]
                
#         return maxstring
        
        
        
        
#         m = \"\" 
#         for i in range(len(s)): 
#             m = max(m, s[i:]) 
  
#         return m




class Solution:
    def lastSubstring(self, s: str) -> str:      
        c, n = max(s), len(s)
        if s == c*n:
            return s
        
        q = [i for i, e in enumerate(s) if e == c]
        res = s[q[0]]
        while q:
            qq = []
            for i in q:
                if i+1 < n:
                    qq += [i+1]
            if not qq:
                break
            c = max(s[i] for i in qq)
            res += c
            q = [i for i in qq if s[i] == c]
        
        return res        

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j, offset = 0,1,0
        
        
        while (i+offset < len(s)) and (j+offset < len(s)):
            if s[i+offset] == s[j+offset]:
                offset += 1
            else:
                if s[i+offset] < s[j+offset]:
                    i += offset +1
                elif s[i+offset] > s[j+offset]:
                    j += offset + 1
                
                if i == j:
                    i += 1
                offset = 0
        loc = min(i,j)
        return s[loc:]
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        c = s[0]
        for num in range(len(s)):
            if s[num] > c:
                i = num
                c = s[num]
        j = i + 1
        k = 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
            elif s[i+k] > s[j+k]:
                j += k + 1
                k = 0
            else:
                i = j
                j = i + 1
                k = 0
                
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        c, n = max(s), len(s)
        if s == c*n:
            return s
        
        q = [i for i, e in enumerate(s) if e == c]
        res = s[q[0]]
        while q:
            qq = []
            for i in q:
                if i+1 < n:
                    qq += [i+1]
            if not qq:
                break
            c = max(s[i] for i in qq)
            res += c
            q = [i for i in qq if s[i] == c]
        
        return res        

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0        
        while j+k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
                i = max(i+k+1, j)
                j = i+1
            k = 0
        return s[i:]

class Solution:       
    def lastSubstring(self, s: str) -> str:
        curr_value = 0
        max_value = 0
        max_idx = 0
        char_to_id = {c: i for i, c in enumerate(sorted(set(s)))}
        
        for i in range(len(s) - 1, -1, -1):
            curr_value = char_to_id[s[i]] + curr_value / len(char_to_id) # Note, uses floating point.

            if curr_value > max_value:
                max_value = curr_value
                max_idx = i

        return s[max_idx:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # i: starting index of the first substring
        i = 0
        # j: starting index of the second substring
        j = 1
        # k: length of substring
        k = 0
        
        # the answer must be a consecutive substring start of biggest char
        # if j find better starting index, use it to update i
        n = len(s)
        
        while j+k < n:
            ## cannot compare now, compare at next char
            if s[i+k] == s[j+k]:
                k+=1
                continue
            ## i is bigger, j should find next candidate
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
            ## j is bigger, i should find next candidate
                i = i+k+1
            if i == j:
            ## update i with j, j keep searching
                j += 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i + k] > s[j + k]:
                j = j + 1
            elif s[i + k] < s[j + k]:
                i = i + 1
            if i == j:
                j = j + 1
            k = 0
            
        
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
                continue
            if s[i + k] > s[j + k]:
                j = j + k + 1
            else:
                i = max(i + k + 1, j)
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s):
        i, j, inc = 0, 1, 0
        while j + inc < len(s):
          if i + inc == j:
            j = j + inc
            inc = 0
          elif s[j + inc] > s[i]:
            i = j + inc
            j = i + 1
            inc = 0
          elif s[i + inc] == s[j + inc]:
            inc += 1
          elif s[i + inc] < s[j + inc]:
            i = j
            j += 1
            inc = 0
          else:
            j += max(inc, 1)
            inc = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    i += 1
                offset = 0
        return s[min(i, j):]
    


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = i + k + 1
            if i == j:
                j = j + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:  
        n = len(s)
        max_char = max(s)
        max_index = None
        for i, x in enumerate(s):
            if x == max_char:
                if max_index is None:
                    max_index = i
                elif i>0 and s[i-1] != max_char:
                    cand1 = max_index+1
                    cand2 = i+1
                    while cand2 < n and s[cand1] == s[cand2]:
                        cand1 += 1
                        cand2 += 1
                    if cand2 == n: 
                        continue
                    if s[cand1] < s[cand2]:
                        max_index = i
        return s[max_index:]
                    


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        candidate_indices = list(range(len(s)))
        offset = 0
        
        while len(candidate_indices) > 1:
            current_max = max([s[candidate + offset] for candidate in candidate_indices if candidate + offset < len(s)])
            new_candidates = []
            
            for i, candidate in enumerate(candidate_indices):
            
                if i >= 1 and candidate_indices[i - 1] + offset == candidate:
                    # Swallow
                    continue
                
                if candidate + offset >= len(s):
                    break
                
                if s[candidate + offset] == current_max:
                    new_candidates.append(candidate)
                
            
            candidate_indices = new_candidates
            offset += 1
        
        return s[candidate_indices[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i + k] == s[j + k]:
                k += 1
                continue
            elif s[i + k] < s[j + k]:
                i = max(j, i + k + 1)
                j = i + 1
                k = 0
            else:
                j += 1 
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i :]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        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]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # Keep track of the candidates for the maximum substring
        # then compare the next characters of the current candidates
        # and update the candidates list in which all candidates are equally likely to be the maximum subtring
        # if the length of the candidates list is equal to 1, then the candidate is the maximum subtstring
        
        candidate_indices = list(range(len(s))) # at the start, every substring is a candidate 
        index_offset = 0 # will be used to compare the next characters of the candidates
        
        while len(candidate_indices) > 1:  # Loop until we have more than one candidate
            # Using Python List Comprehension to find the maximum of the next char of the candidate
            current_max = max([s[candidate + index_offset] for candidate in candidate_indices if candidate + index_offset < len(s)])
            
            new_candidates = [] # used to update the candidates list
            
            # Find the starting index of the current_max character, i.e., finding the new list of candidates
            for i, candidate in enumerate(candidate_indices):
                
                # if the last char of the previous candidate is the start of the current candidate,
                # merge them together as one candidate
                if i > 0 and candidate_indices[i - 1] + index_offset == candidate: 
                    continue # Do not need to add the current candidate as the previous is added
                
                if candidate + index_offset > len(s) - 1: # we are out of bounds, need to break the loop
                    break
                
                if s[candidate + index_offset] == current_max: # found the candidate which has the current_max
                    new_candidates.append(candidate) # append the starting index of the current best candidate
            
            candidate_indices = new_candidates # Update the candidates
            index_offset += 1 # Consider the next character
        
        # if we are here, it means we have only one candidate, which is the starting index of the maximum substring 
        return s[candidate_indices[0]:] 
            



#         # The Naive Solution
#         # Keep track of the maximum string in a separate variable
#         # Do this for every character at index `i`  in string `s` like the following: s[i:]
#         # The drawback: string comparison takes O(n) time, and we need to do for every string
#         # starting with character at index `i`. So the overall time complexity would be
#         # O(n^2) - which is not good.
        
#         max_substring = \"\" # max_substring means the last substring in lexicographical order
        
#         for i in range(len(s)): # iterate over every character in the string
#             max_substring = max(s[i:], max_substring) # update the maximum substring if the new subtring is greater
        
#         return max_substring # return the maxium substring


# class Solution:
#     def lastSubstring(self, s: str) -> str:
#         #给的提示是用后缀树
#         #因为必定是后缀才满足最后一个字典序
#         #当然也包括它本身
#         #字典序就是下一个比它大的数或者字符串，可以有环，环首是最小的
        
        
        
        
class Solution:
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        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]:]
        
        
        
        
        
        
        
        
        
        
        
        
        
#         graph = defaultdict(list)
#         cur = 'a'
#         for idx, val in enumerate(s):
#             if cur < val:
#                 cur = val
#             graph[val].append(idx)
        
#         maxstartst = graph[cur]
#         rt = ''
#         nxt = ord(cur)
#         end = ord('a')
#         while nxt >= end:
#             nxtchar = chr(nxt)
#             if nxtchar in graph:
#                 for item in graph[nxtchar]:
#                     temp = bisect.bisect_right(maxstartst, item-1)
#                     if maxstartst[temp-1] == item -1:
#                         return s[maxstartst[temp-1]:]
            
#             nxt-=1

#         return rt


class Solution:
    def lastSubstring(self, s: str) -> str:
        # Keep track of the candidates for the maximum substring
        # then compare the next characters of the current candidates
        # and update the candidates list in which all candidates are equally likely to be the maximum subtring
        # if the length of the candidates list is equal to 1, then the candidate is the maximum subtstring
        
        candidate_indices = list(range(len(s))) # at the start, every substring is a candidate 
        index_offset = 0 # will be used to compare the next characters of the candidates
        
        while len(candidate_indices) > 1:  # Loop until we have more than one candidate
            # Using Python List Comprehension to find the maximum of the next char of the candidate
            current_max = max([s[candidate + index_offset] for candidate in candidate_indices if candidate + index_offset < len(s)])
            
            new_candidates = [] # used to update the candidates list
            
            # Find the starting index of the current_max character, i.e., finding the new list of candidates
            for i, candidate in enumerate(candidate_indices):
                
                # if the last char of the previous candidate is the start of the current candidate,
                # merge them together as one candidate
                if i > 0 and candidate_indices[i - 1] + index_offset == candidate: 
                    continue # Do not need to add the current candidate as the previous is added
                
                if candidate + index_offset > len(s) - 1: # we are out of bounds, need to break the loop
                    break
                
                if s[candidate + index_offset] == current_max: # found the candidate which has the current_max
                    new_candidates.append(candidate) # append the starting index of the current best candidate
            
            candidate_indices = new_candidates # Update the candidates
            index_offset += 1 # Consider the next character
        
        # if we are here, it means we have only one candidate, which is the starting index of the maximum substring 
        return s[candidate_indices[0]:]
        
        # TIME and SPACE Complexities: O(n), where n - the length of the string
            



#         # The Naive Solution
#         # Keep track of the maximum string in a separate variable
#         # Do this for every character at index `i`  in string `s` like the following: s[i:]
#         # The drawback: string comparison takes O(n) time, and we need to do for every string
#         # starting with character at index `i`. So the overall time complexity would be
#         # O(n^2) - which is not good.
        
#         max_substring = \"\" # max_substring means the last substring in lexicographical order
        
#         for i in range(len(s)): # iterate over every character in the string
#             max_substring = max(s[i:], max_substring) # update the maximum substring if the new subtring is greater
        
#         return max_substring # return the maxium substring


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        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]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        slow,compareCnt,n=0,0,len(s)
        for fast in range(1,n):
            if s[fast]!=s[slow+compareCnt] or slow+compareCnt==fast-compareCnt-1:
                if s[fast]>s[slow+compareCnt]:
                    slow=fast if s[fast]>s[slow] else fast-compareCnt
                compareCnt=0
            else:
                compareCnt+=1
        return s[slow:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        step = 0
        index = [i for i in range(len(s))]

        biggest_letter = 'a'
        for i in index:
            if s[i + step] > biggest_letter:
                biggest_letter = s[i + step]

        buff_index = []
        for i in index:
            if (s[i + step] == biggest_letter) & (i + step < len(s)):
                if i==0:
                    buff_index.append(i)
                if  ((i!=0) and (s[i-1]!=s[i])):
                    buff_index.append(i)
        index = buff_index
        step += 1


        while (len(index) > 1):
            biggest_letter = 'a'
            for i in index:
                if i+step < len(s):
                    if s[i+step] > biggest_letter:
                        biggest_letter = s[i+step]

            buff_index = []
            for i in index:
                if i + step < len(s):
                    if (s[i+step] == biggest_letter) & (i+step<len(s)):
                        buff_index.append(i)

            index = buff_index

            step += 1


        res = s[index[0]:len(s)]

        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        
        
        while len(indexes) > 1:
            new = []
            mx = max([s[i + j] for j in indexes if i + j < len(s)])
            print(mx)
            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]:]

class Solution:
    # build the suffix tree of the string and traverse the tree by always pick the right most branch.
    def lastSubstring(self, s: str) -> str:
        class TreeNode:
            def __init__(self):
                self.children = collections.defaultdict()

        # build the suffix tree
        root = TreeNode()
        for start in range(len(s)):
            node = root
            for c in s[start:]:
                if c not in node.children:
                    node.children[c] = TreeNode()
                node = node.children[c]
        # traverse the tree
        res = ''
        node = root
        while node and len(node.children) > 0:
            for i in range(25, -1, -1):  # find the rightmost available branch
                c = chr(ord('a') + i)
                if c in node.children:
                    node = node.children[c]
                    res += c
                    break
        return res
    
    # It can be seen that the last substring in lexicographical order is always a suffix of the string.
    # Start with all possible suffix strings. Each time eliminate the ones not started from the largest letter.
    # Continue until there is only one distinct letter.
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        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]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        starts = list(range(len(s)))
        offset = 0
        while len(starts) > 1:
            newstarts = []
            end = max(s[start + offset] for start in starts if start + offset < len(s))
            for i, ch in enumerate(starts):
                if i > 0 and starts[i - 1] + offset == starts[i]:
                    continue
                if ch + offset == len(s):
                    break
                if s[ch + offset] == end:
                    newstarts.append(ch)
            offset += 1
            starts = newstarts
        return s[starts[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, indexes = 0, list(range(len(s)))
        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]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        # we will be calling this a lot
        lenS = len(s)
        
        # find the lexicographically biggest character
        largestChar = max(set(s))
        
        # find the start of potential max substrings and store in candidates
        # also, make sure to ignore repeats (i.e. aaaaaaaaa.....)
        candidateIndexes = []
        repeating = False
        for i in range(lenS):
            if s[i] == largestChar:
                if repeating == False:
                    candidateIndexes.append(i)
                    repeating = True
            else:
                repeating = False
        
        # go through the candidates, see which one is the best
        bestCandidateIndex = candidateIndexes[0]
        for i in range(1, len(candidateIndexes)):
            counter = 1
            index = candidateIndexes[i]
            while bestCandidateIndex + counter < lenS and index + counter < lenS:
                if s[index + counter] > s[bestCandidateIndex + counter]:
                    bestCandidateIndex = index
                    break
                elif s[index + counter] == s[bestCandidateIndex + counter]:
                    counter += 1
                    continue
                else:
                    break
            
        return s[bestCandidateIndex:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        step = 0
        index = []

        biggest_letter = 'a'
        for i in range(len(s)):
            if s[i + step] > biggest_letter:
                biggest_letter = s[i + step]

        buff_index = []
        for i in range(len(s)):
            if (s[i + step] == biggest_letter) & (i + step < len(s)):
                if i==0:
                    buff_index.append(i)
                if  ((i!=0) and (s[i-1]!=s[i])):
                    buff_index.append(i)
        index = buff_index
        step += 1


        while (len(index) > 1):
            biggest_letter = 'a'
            for i in index:
                if i+step < len(s):
                    if s[i+step] > biggest_letter:
                        biggest_letter = s[i+step]

            buff_index = []
            for i in index:
                if i + step < len(s):
                    if (s[i+step] == biggest_letter) & (i+step<len(s)):
                        buff_index.append(i)

            index = buff_index

            step += 1


        res = s[index[0]:len(s)]

        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            else:
                if s[i + k] > s[j + k]:
                    j = j + k + 1
                else:
                    i = i + k + 1
                if i == j:
                    j = j + 1
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,offset = 0,1,0
        
        while i+offset<len(s) and j+offset<len(s):
            if s[i+offset]==s[j+offset]:
                offset+=1
                
            else:
                if s[i+offset]<s[j+offset]:
                    i+=1
                else:
                    j+=1
                    
                if i==j:
                    j+=1
                    
                offset=0
                
        return(s[i:])

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i :]


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxchr = max(s)
        index = []
        maxstring = ''
        i = 0
        while i < len(s):
            if s[i] == maxchr:
                if i == 0 or s[i] != s[i-1]:
                    index.append(i)
                    maxstring = max(maxstring, s[i:])
            i += 1
        return maxstring

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        starts = list(range(n))
        offset = 0
        while len(starts) > 1:
            max_end = max(s[start + offset] for start in starts if start + offset < n)
            new_starts = []
            for i, start in enumerate(starts):
                if i > 1 and starts[i - 1] + offset == start:
                    # swallow
                    continue
                if start + offset == n:
                    # end of s
                    break
                if s[start + offset] == max_end:
                    new_starts.append(start)
            offset += 1
            starts = new_starts
        return s[starts[0]:]  

class Solution:
    def lastSubstring(self, s: str) -> str:
        if len(set(s))==1:
            return s
        alpha=sorted(list(set(s)))
        start=alpha[-1]
        
        n=len(s)
        index=[]
        for i,char in enumerate(s):
            if char==start:
                index.append(i)
            
        prefix=start
        maxprefix=start
        while len(index)>1:
            nextindex=[]
            for i in index:
                if i+1<n:
                    if prefix+s[i+1]==maxprefix:
                        maxprefix=prefix+s[i+1]
                        nextindex.append(i+1)
                    elif prefix+s[i+1]>maxprefix:
                        maxprefix=prefix+s[i+1]
                        nextindex=[i+1]
            prefix=maxprefix
            index=nextindex
        
        
        return maxprefix+s[index[0]+1:]
                    


class Solution:
    def lastSubstring(self, s: str) -> str:
        n, pointer = len(s), 0 #pointer points to the char we're comparing in candidiates
        starts = list(range(n)) #starts is starting points of candidates 
        while len(starts)>1: #more than one candidiate
            max_end = max([s[start+pointer] for start in starts if start+pointer < n]) #max val for pointer
            new_starts = [] #starts with max_end this round are filtered to compare for next round
            for i, start in enumerate(starts):
                if i>1 and starts[i-1]+pointer == start:
                    continue # when prev candidate's pointer meets cur's start, cur is def less than prev
                elif start+pointer == n:
                    break #reaches end, no valid new new val
                if s[start+pointer] == max_end:
                    new_starts.append(start)
            pointer += 1
            starts = new_starts
        return s[starts[0]:]
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        starts = list(range(n))
        offset = 0
        while len(starts) > 1:
            max_end = max(s[start + offset] for start in starts if start + offset < n)
            new_starts = []
            for i, start in enumerate(starts):
                if i > 1 and starts[i - 1] + offset == start:
                    # swallow
                    continue
                if start + offset == n:
                    # end of s
                    break
                if s[start + offset] == max_end:
                    new_starts.append(start)
            offset += 1
            starts = new_starts
        return s[starts[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        pos = defaultdict(list)
        large = 'a'
        for i, c in enumerate(s):
            pos[c].append(i)
            large = max(large, c)
            
        remain = set(pos[large]); sz = 1
        #print(remain)
        while len(remain) > 1:
            large = ''
            for idx in remain:
                if idx+sz < len(s) and s[idx+sz] > large:
                    large = s[idx+sz]
            
            to_remove = set()
            for idx in remain:
                if idx+sz in remain:
                    to_remove.add(idx+sz)
                if idx+sz >= len(s) or s[idx+sz] != large:
                    to_remove.add(idx)
            remain -= to_remove
            sz += 1
        idxs = [a for a in remain]
        return s[idxs[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0    
        while i+offset<len(s) and j+offset<len(s):
            if s[i+offset]==s[j+offset]:
                offset+=1                
            else:
                if s[i+offset]<s[j+offset]:
                    i+=offset+1
                else:
                    j+=offset+1
                    
                if i==j:
                    j+=1
                offset = 0
                    
        return(s[i:])
    
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        n, offset = len(s), 0
        starts = list(range(n))
        while len(starts) > 1:
            max_end = max(s[start + offset] for start in starts if start + offset < n)
            new_starts = []
            for i, start in enumerate(starts):
                if i > 1 and starts[i - 1] + offset == start: continue
                if start + offset == n: break
                if s[start + offset] == max_end: new_starts += start,
            offset += 1
            starts = new_starts
        return s[starts[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        starts = list(range(n))
        offset = 0
        while len(starts) > 1:
            max_end = max(s[start + offset] for start in starts if start + offset < n)
            new_starts = []
            for i, start in enumerate(starts):
                if i > 1 and starts[i - 1] + offset == start:
                    # swallow
                    continue
                if start + offset == n:
                    # end of s
                    break
                if s[start + offset] == max_end:
                    new_starts.append(start)
            offset += 1
            starts = new_starts
        return s[starts[0]:] 

class Solution:
    def lastSubstring(self, s: str) -> str:
        # Create a suffix array, and sort it to fetch the biggest one
#         suffix_array = []
        
#         for idx in range(len(s)):
#             suffix_array.append(s[idx:])
        
#         suffix_array.sort()
        
#         return suffix_array[-1]
        # O(n^2)
    
        n = len(s)
        starts = list(range(n))
        offset = 0
        
        while len(starts) > 1:
            max_end = max(s[start + offset] for start in starts if start + offset < n)
            new_starts = []
            for idx, start in enumerate(starts):
                if idx > 1 and starts[idx - 1] + offset == start:
                    # swallow
                    continue
                if start + offset == n:
                    # end of s
                    break
                if s[start + offset] == max_end:
                    new_starts.append(start)
            offset += 1
            starts = new_starts
        return s[starts[0]:]         


# class Solution:
#     def lastSubstring(self, s: str) -> str:
        
        
#         stack = []
#         dic = {}
#         for i in 'abcdefghijklmnopqrstuvwxyz':
#             dic[ord(i)] = i
#         right = 0
#         while right < len(s):
#             if not stack:
#                 stack.append(ord(s[right]))
#             else:
#                 if ord(s[right]) > stack[0]:
#                     stack = []
#                 elif ord(s[right]) == stack[0]:
#                     index = 0
#                     while right + index < len(s) and index < len(stack):
#                         if ord(s[right+index]) > stack[index]:
#                             stack = []
#                             break
#                         elif ord(s[right+index]) < stack[index]:
#                             break
                        
#                         index += 1
#                 stack.append(ord(s[right]))
#             right += 1
            
        
#         res = ''
        
#         for i in stack:
#             res += dic[i]
            
#         return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        ## get max char from s
        maxC, N = max(s),len(s)
        ## get max char indexs to append into inds
        ## only store the first ind for consecutive max chars
        inds = [i for i in range(N) if s[i]==maxC and (i==0 or s[i-1]!=maxC)]
        maxind = inds[0] # starting index of the max substring
       
        ## using for loop to compare with each substring lead by max char
        for i in range(1,len(inds)):
            curind = inds[i] # start index of current substring
            step = 0 # index pointer from start index
            ## compare the current sub with the max sub string
            while curind+step<N:
                if s[curind+step]>s[maxind+step]: # current sub larger than maxsub
                    maxind = curind
                    break
                elif s[curind+step]==s[maxind+step]:
                    step += 1
                else: # s[curind+step]<s[maxind+step]: # current sub smaller than maxsub
                    break
                
        return s[maxind:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        cand = list(range(len(s)))
        ans = ''
        step = 0
        while len(cand) > 1:
            nxt = []
            tmp = None
            for x in cand:
                if tmp is None or ord(s[x]) > ord(tmp):
                    tmp = s[x]
            ans += tmp
            for x in cand:
                if tmp == s[x]:
                    if x + 1 < len(s) and (len(nxt) == 0 or nxt[-1] < x - step):
                        nxt.append(x + 1)
            cand = nxt
            step += 1
        if len(cand) == 0:
            return ans
        return ans + s[cand[0]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        # Create a suffix array, and sort it to fetch the biggest one
#         suffix_array = []
        
#         for idx in range(len(s)):
#             suffix_array.append(s[idx:])
        
#         suffix_array.sort()
        
#         return suffix_array[-1]
        # O(n^2)
    
        n = len(s)
        offset = 0
        cand_starts = list(range(len(s)))
        
        while len(cand_starts) > 1: # Find one and only start
            max_end = 'a'
            
            for start in cand_starts:
                if start + offset < n: 
                    max_end = max(max_end, s[start + offset])            
        
            new_starts = []
            
            for idx, start in enumerate(cand_starts):
                # start is actual idx, idx is relative ordering of start points
                # Check if previous start merges other start. In that case we wnat to merge these cases
                    # Show ex of Ex1, Ex2
                    if 1 < idx and cand_starts[idx - 1] + offset == start:
                        # Previous start point collapes with new one. Merged
                        continue
                    
                    if start + offset == n:
                        break 
                        # It went over the length list. Break
                    
                    if s[start+offset] == max_end:
                        new_starts.append(start)
                        
            cand_starts = new_starts
            offset += 1
                    
            
        
        return s[cand_starts[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        arrSize = len(s)
        suffArr = []
        
        # first construct a suffix array
        for i in s:
            suffArr.append(ord(i))
            
        if (len(list(set(suffArr)))) == 1:
            print((len(s)))
            return s
            
        sumArr = [0] * arrSize
        sumArr[-1] = suffArr[-1]
        
        for i in range(arrSize - 2, -1, -1):
            sumArr[i] = sumArr[i + 1] + suffArr[i]
        
        blockSize = 1
        currArr = suffArr[:]
        
        ret = 0
        
        while True:
            maxNum = max(currArr) # find the max value
            maxInds = []
            
            # find all the maximum indices
            for i in range(len(currArr)):
                if maxNum == currArr[i]:
                    maxInds.append(i)
                        
            # if there's only one entry
            if len(maxInds) == 1:
                return str(s[maxInds[0]:])
            
            blockSize += 1

            # otherwise, we have to keep comparing
            for i in maxInds:
                if i + blockSize >= arrSize:
                    currArr[i] = sumArr[i]    
                else:
                    currArr[i] = sumArr[i] - sumArr[i + blockSize]
            
        return None            


class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        ss = list(map(lambda x: ord(x) - ord('a'), s))
        xmax = max(ss)
        xs = [(x, i, i + 1) for i, x in enumerate(ss) if x == xmax]
        while len(xs) > 1:
            xt, xmax = [], -1
            for h, i, j in xs:
                if ((not xt) or xt[-1][2] <= i) and j < n:
                    if ss[j] > xmax:
                        xt = [(h * 26 + ss[j], i, j + 1)]
                        xmax = ss[j]
                    elif ss[j] == xmax:
                        xt.append((h * 26 + ss[j], i, j + 1))
                    xs = xt
        return s[xs[0][1]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        lastc = max(s)
        n = len(s)
        q = [i for i,val in enumerate(s) if val==lastc]
        if len(q) == len(s):
            return s
        res = s[q[0]]
        while q:
            qq = []
            for i in q:
                if i+1 < n:
                    qq += [i+1]
            if not qq:
                break
            c = max(s[i] for i in qq)
            res += c
            q = [i for i in qq if s[i] == c]
        
        return res
    # def lastSubstring(self, s: str) -> str:
    # \tS, L, a = [ord(i) for i in s] + [0], len(s), 1
    # \tM = max(S)
    # \tI = [i for i in range(L) if S[i] == M]
    # \tif len(I) == L: return s
    # \twhile len(I) != 1:
    # \t\tb = [S[i + a] for i in I]
    # \t\tM, a = max(b), a + 1
    # \t\tI = [I[i] for i, j in enumerate(b) if j == M]
    # \treturn s[I[0]:]
        
        #ans = [s[i:] for i in lead]
        # print(ans)
        # start = s.index(lastc)
        # while s[start]:
        #     print(start)
        #     ans.append(s[start:])
        #     print(ans)
        #     if s[start+1:].count(lastc) == 0:
        #         break
        #     else:
        #         start += s[start+1:].index(lastc) + 1
        # print(ans)
        return sorted(ans)[-1]


class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        offset = 0
        cand_starts = list(range(len(s)))
        
        while len(cand_starts) > 1: # Find one and only start
            max_end = 'a'
            
            for start in cand_starts:
                if start + offset < n: 
                    max_end = max(max_end, s[start + offset])            
        
            new_starts = []
            
            for idx, start in enumerate(cand_starts):
                # start is actual idx, idx is relative ordering of start points
                # Check if previous start merges other start. In that case we wnat to merge these cases
                    # Show ex of Ex1, Ex2
                    if 1 < idx and cand_starts[idx - 1] + offset == start:
                        # Previous start point collapes with new one. Merged
                        continue
                    
                    if start + offset == n:
                        break 
                        # It went over the length list. Break
                    
                    if s[start+offset] == max_end:
                        new_starts.append(start)
                        
            cand_starts = new_starts
            offset += 1
                    
            
        
        return s[cand_starts[0]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        max_letter = max(s)
        pre_letter = None
        
        current_max = max_letter
        for i, c in enumerate(s):
            if c == max_letter and pre_letter != c:
                current_max = max(current_max, s[i:])
            pre_letter = c
            
        
        return current_max

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        ## get max char from s
        maxC, N = max(s),len(s)
        ## get max char indexs to append into inds
        ## only store the first ind for consecutive max chars
        inds = [i for i in range(N) if s[i]==maxC and (i==0 or s[i-1]!=maxC)]
        maxind = inds[0] # starting index of the max substring
        
        for i in range(1, len(inds)):
            cur_sub_start = inds[i]
            pointer = 0
            while cur_sub_start + pointer < N:
                if s[cur_sub_start + pointer] > s[maxind + pointer]:
                    maxind = inds[i]
                    break
                elif s[cur_sub_start + pointer] == s[maxind + pointer]:
                    pointer += 1
                else:
                    break
        return s[maxind:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i :]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,k=0,1,0
        n=len(s)
        while j+k<n:
            
            if s[i+k]==s[j+k]:
                k+=1
                continue
            elif s[i+k]>s[j+k]:
                j=j+k+1
            else:
                # i=max(j,i+k+1)
                i = i+k+1
                j=i+1
            k=0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = i + k + 1
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # sort of like a sliding window, where length is substr / window size
        left, right, length = 0, 1, 0
        n = len(s)
        while right + length < n:
            # print(left, right, length)
            # print(s[left + length], s[right + length])
            if s[left + length] == s[right + length]:
                # substrings so far are the same
                length += 1
            elif s[left + length] > s[right + length]:
                # first substring is more optimal, capture entire
                # left substring + right substrings
                right += length + 1
                length = 0
            else:
                # right substring is more optimal
                # left = max(left + length + 1, right) # this is confusing
                left += length + 1
                # aabc
                # lr, length 1
                # lr, length 2 -> aa and ab -> advance to left + length + 1
                # aaabc
                # lr, length 3 -> aaa and aab -> 
                
                right = left + 1
                length = 0
                
        return s[left:]
        
        
        
        
        
        
        
        # this is slow..
#         n = len(s)
#         answer = \"\"
        
#         for i in range(n):
#             # can't hurt to just go all the way to the end of the string
#             answer = max(answer, s[i:])

#         return answer


class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        offset = 0
        cand_starts = list(range(len(s)))
        
        while len(cand_starts) > 1: # Find one and only start
            max_end = 'a'
            
            for start in cand_starts:
                if start + offset < n: 
                    max_end = max(max_end, s[start + offset])            
        
            new_starts = []
            
            for idx, start in enumerate(cand_starts):
                # start is actual idx, idx is relative ordering of start points
                # Check if previous start merges other start. In that case we wnat to merge these cases
                    # Show ex of Ex1, Ex2
                    if 1 < idx and cand_starts[idx - 1] + offset == start:
                        # Previous start point collapes with new one. Merged
                        continue
                    
                    if start + offset == n:
                        break 
                        # It went over the length list. Break
                    
                    if s[start+offset] == max_end:
                        new_starts.append(start)
                        
            cand_starts = new_starts
            offset += 1
                    
            
        
        return s[cand_starts[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # Algorithm
        # First look for the max letter starting points
        i, j, k = 0, 1, 0
        N = len(s)      
        
        while j + k < N:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
                i = i+k+1
                j = i+1
            k = 0
        return s[i:]
#         max_letter = None
#         indexes = []
#         for i, c in enumerate(s):
#             if max_letter is None or c > max_letter:
#                 max_letter = c
#                 indexes = [(i, i+1)]
#             elif max_letter == c:
#                 indexes.append((i, i+1))
                
#         # Now we iterate over them like a queue
#         while len(indexes) != 1:
#             new_indexes = []
#             new_max_letter = None
            
#             for tup in indexes:
#                 if tup[1] >= len(s):
#                     continue
                          
#                 if new_max_letter is None or s[tup[1]] > new_max_letter:
#                     new_indexes = [(tup[0], tup[1] + 1)]
#                     new_max_letter = s[tup[1]]
#                 elif s[tup[1]] == new_max_letter:
#                     new_indexes.append((tup[0], tup[1] + 1))
#             indexes = new_indexes
        
#         return s[indexes[0][0]:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        if len(s)==1:return s
        
        res=[]
        
        max_char=s[0]
        res.append(0)
        i=1
        while i<=len(s)-1:
            if s[i]>max_char:
                res=[i]
                max_char=s[i]
            elif s[i]==max_char:
                if s[i-1] != max_char:res.append(i)
            i+=1
        
        while len(res)>1:
            p0=res[0]
            p1=res[1]
            count=1
            while p0+count<p1:
                if p1+count>len(s)-1:
                    return s[res[0]:]
                if s[p0+count]>s[p1+count]:
                    res.pop(1)
                    break
                elif s[p0+count]<s[p1+count]:
                    res.pop(0)
                    break
                else:count+=1
            if p0+count==p1: res.pop(1)
         
        return s[res[0]:]
                
            
            
                    
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
               # i = max(i + k + 1, j)
                i = i+k+1
                j = i + 1
            k = 0
        return s[i:]


# class Solution:
#     def lastSubstring(self, s: str) -> str:
        
        
#         stack = []
#         dic = {}
#         for i in 'abcdefghijklmnopqrstuvwxyz':
#             dic[ord(i)] = i
#         right = 0
#         while right < len(s):
#             if not stack:
#                 stack.append(ord(s[right]))
#             else:
#                 if ord(s[right]) > stack[0]:
#                     stack = []
#                 elif ord(s[right]) == stack[0]:
#                     index = 0
#                     while right + index < len(s) and index < len(stack):
#                         if ord(s[right+index]) > stack[index]:
#                             stack = []
#                             break
#                         elif ord(s[right+index]) < stack[index]:
#                             break
                        
#                         index += 1
#                 stack.append(ord(s[right]))
#             right += 1
            
        
#         res = ''
        
#         for i in stack:
#             res += dic[i]
            
#         return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        ## get max char from s
        maxC, N = max(s),len(s)
        ## get max char indexs to append into inds
        ## only store the first ind for consecutive max chars
        inds = [i for i in range(N) if s[i]==maxC and (i==0 or s[i-1]!=maxC)]
        print(inds)
        maxind = inds[0] # starting index of the max substring
       
        ## using for loop to compare with each substring lead by max char
        for i in range(1,len(inds)):
            curind = inds[i] # start index of current substring
            step = 0 # index pointer from start index
            ## compare the current sub with the max sub string
            while curind+step<N:
                if s[curind+step]>s[maxind+step]: # current sub larger than maxsub
                    maxind = curind
                    break
                elif s[curind+step]==s[maxind+step]:
                    step += 1
                else: # s[curind+step]<s[maxind+step]: # current sub smaller than maxsub
                    break
                
        return s[maxind:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        split = []
        cur = [s[0], 0]
        for i in range(1, len(s)):
            if ord(s[i]) > ord(s[i-1]):
                split.append(cur)
                cur = [s[i], i]
            else:
                cur[0] += s[i]
        split.append(cur)
        split = sorted(split, key=lambda x: x[0], reverse=True)
        return s[split[0][1]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if len({l for l in s})==1: return s
        arr = self.sort_bucket(s, (i for i in range(len(s))), 1)
        return s[arr[-1]:]

    def sort_bucket(self, s, bucket, order):
        d = defaultdict(list)
        for i in bucket:
            key = s[i:i+order]
            d[key].append(i)
        result = []
        for k, v in sorted(d.items()):
            if len(v) > 1:
                result += self.sort_bucket(s, v, order*2)
            else:
                result.append(v[0])
        return result

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return ''
        if len(set(s)) == 1: return s
        largest = max(list(s))
        currmax = ''
        for i,c in enumerate(s):
            if c == largest:
                if s[i:] > currmax:
                    currmax = s[i:]       
        return currmax
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = 1
        k = 0
        n = len(s)
        
        while j+k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = max(i+k+1, j)
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        c = s[0]
        for num in range(len(s)):
            if s[num] > c:
                i = num
                c = s[num]
        j = i + 1
        k = 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j += k + 1
            else:
                i += k + 1
                j = i + 1
            k = 0
                
        return s[i:]

def analize(arr):
    curstr = 1;
    streaks = {}
    strstart = arr[0]
    for ii,val in enumerate(arr[:-1]):
        if arr[ii]==arr[ii+1]-1:
            curstr +=1
        else:
            streaks[strstart] = curstr
            strstart = arr[ii+1]
            curstr = 1
    streaks[strstart] = curstr
    maxstr = max(streaks.values())
    return([(ii,maxstr) for ii in streaks if streaks[ii]==maxstr])

class Solution:
    def lastSubstring(self, s: str) -> str:
        index = {}
        for char in set(s):
            index[char] = [ic for ic,cc in enumerate(s) if cc == char]             
#        print(index)
#        return 'a'
        maxchar = max(index.keys())    
        front = analize(index[maxchar])
        curbest = ''
#        print(front,len(s))
        while front!=[]:
            curbest = curbest+s[front[0][0]]*front[0][1]
            nxt = [s[u[0]+u[1]] for u in front if u[0]+u[1]<len(s)]
#            print(front,curbest,nxt)
#            return 'a'
            if nxt!=[]:
                maxnxt = max(nxt)
                front = [(u[0]+u[1],1) for u in front if u[0]+u[1]<len(s) and s[u[0]+u[1]] == maxnxt]
            else:
                front = []
        return curbest            

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        c = s[0]
        for num in range(len(s)):
            if s[num] > c:
                i = num
                c = s[num]
        j = i + 1
        k = 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
            elif s[i+k] > s[j+k]:
                j += k + 1
                k = 0
            else:
                i += k + 1
                j = i + 1
                k = 0
                
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        ls=max(set(s))
        best_symbol=s.index(ls)
        first_symbol=best_symbol
        f=first_symbol
        while s[best_symbol] in s[first_symbol+1:]:
            next_symbol=s.index(s[best_symbol],first_symbol+1)
            next_symbol_=next_symbol
            f_=f
            while next_symbol_<len(s) and s[f_]==s[next_symbol_]:
                f_+=1
                next_symbol_+=1

            if next_symbol_<len(s) and s[f_]<s[next_symbol_]:
                f=next_symbol
            elif next_symbol_==len(s):
                break
            first_symbol=next_symbol
        return s[f:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not len(s): return s
        temp = s[0]
        for i in range(1,len(s)):
            if s[i:min(i+len(temp), len(s))] > temp:
                temp = s[i]
            else:
                temp += s[i]
        return temp
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        if not len(s): return s
        temp = s[0]
        for i in range(1,len(s)):
            # print(i, temp, \"blah\")
            # print(i, s[i:min(i+len(temp), len(s))])
            if s[i:min(i+len(temp), len(s))] > temp:
                temp = s[i]
            else:
                temp += s[i]
        # print(temp)
        return temp
        


class Solution:  
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset = offset + 1
            else:
                if s[i + offset] < s[j + offset]:
                    i = i + offset + 1
                    j = i + 1
                else:
                    j  = j + offset + 1
                offset = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        index={c:i for i,c in enumerate(sorted(set(s)))}
        radix,opt,curr,i_0=len(index),0,0,0
        for i in range(len(s)-1,-1,-1):
            curr=index[s[i]]+curr/radix
            if curr>opt:
                opt,i_0=curr,i
                
        return s[i_0:]
                
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        #from itertools import permutations 
        #print(''.join(p) for p in permutations(s))
        i,j,k=0,1,0
        n=len(s)
        while j+k<n:
            
            if s[i+k]==s[j+k]:
                k+=1
                continue
            elif s[i+k]>s[j+k]:
                j=j+k+1
            else:
                i=max(j,i+k+1)
                j=i+1
            k=0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_char = s[0]
        for i in range(len(s)):
            if s[i] > max_char:
                max_char = s[i]
            
        cands = []
        for i in range(len(s)):
            if s[i] == max_char:
                cands.append((i+1, i))

        while len(cands) > 1:
            new_cands = []
            max_char = s[cands[0][0]]
            for i in range(len(cands)):
                if cands[i][0] < len(s) and s[cands[i][0]] > max_char: #
                    max_char = s[cands[i][0]]
            
            i = 0
            while i < len(cands):
                if cands[i][0] < len(s) and s[cands[i][0]] == max_char:
                    new_cands.append((cands[i][0]+1, cands[i][1]))
                if i < len(cands)-1 and cands[i][0] == cands[i+1][1]:
                    i += 2
                else:
                    i += 1
                #if cands[i][0]+1 < len(s) and s[cands[i][0]+1] == max_char:
                #    if i>0 and cands[i-1][0]+1 < cands[i][1]:
                #        continue
                #    new_cands.append((cands[i][0]+1, cands[i][1]))
            '''
            skip = False
            for i in range(len(cands)):
                if cands[i][0]+1 < len(s) and s[cands[i][0]+1] == max_char:
                    if skip == True:
                        skip = False
                        continue
                    if i>len(cands)-1 and cands[i][0]+1 >= cands[i+1][1]:
                        skip = True
                    new_cands.append((cands[i][0]+1, cands[i][1]))
            '''
            cands = new_cands
        
        return s[cands[0][1]:] #

class Solution:  
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                    j = i + 1
                else:
                    j += offset + 1
                offset = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        ## get max char from s
        maxC, N = max(s),len(s)
        ## get max char indexs to append into inds
        ## only store the first ind for consecutive max chars
        inds = [i for i in range(N) if s[i]==maxC and (i==0 or s[i-1]!=maxC)]
        maxind = inds[0] # starting index of the max substring
       
        ## using for loop to compare with each substring lead by max char
        for i in range(1,len(inds)):
            curind = inds[i] # start index of current substring
            if self.compare(s[curind:], s[maxind:]):
                maxind = curind
                
        return s[maxind:]
    
    def compare(self, s1, s2):
        i = 0
        while i < len(s1):
            if s1[i] > s2[i]:
                return True
            elif s1[i] < s2[i]:
                return False
            i += 1
        return False
    


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
                i = i+k+1
                j = i+1
            k = 0
        return s[i:]

from collections import Counter
class Solution:
    def lastSubstring(self, s: str) -> str:
        d=Counter(s)
        if(len(d)==1):return s
        c=sorted(d.keys())[-1]
        i=0
        while(s[i]!=c):i+=1
        if(d[c]==1):return s[i:]
        ans=s[i:]
        i+=1
        while(i<len(s)):
            if(s[i]==c and s[i:]>ans):ans=s[i:]
            i+=1
        return ans


'''
case 1:
   a b ...
   i j    => change i to j , j to j+1
case 2:
    cbacbd
    i  j => i==j compare next one
    c b   a  c  b   d
    i i+1    j  j+1  => i==j compare next one
    i=2 < j+2
    i = j 
    j = new_i+1 why? allelemnts are smaller than original i 

'''
class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0,1,0
        while j+k < len(s):
            if s[i+k] > s[j+k]:
                j = j+k+1
                k = 0
            elif s[i+k] == s[j+k]:
                k += 1
            else:
                i = max(i + k + 1, j)
                j = i+1
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_idx = 0
        for i in range(1,len(s)):
            it = s[i]
            max_s = s[max_idx]
            if it >= max_s:
                j = 2
                while(it==max_s):
                    it = s[i:i+j]
                    max_s = s[max_idx:max_idx+j]
                    if i + j == len(s) + 1:
                        if it > max_s:
                            max_idx = i
                        return s[max_idx:]
                    j += 1
                if it>max_s:
                    max_idx = i

        return s[max_idx:]



class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i,j,k = 0,1,0
        while j + k < n:
            if s[i:i+k+1] == s[j:j+k+1]:
                k += 1
            elif s[i:i+k+1] < s[j:j+k+1]:
                i = j
                k = 0
                j = j + 1
            else:
                j += k + 1
                k = 0
        return s[i:j+k]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = min(i + k + 1, j)
                j = i + 1
            k = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        max_ord = 0
        if s.count(s[0])==len(s):
            return s
        for i in range(len(s)):
            max_ord = max(max_ord, ord(s[i]))
        start = chr(max_ord)
        result = ''
        for i in range(s.count(start)):
            substr = s[s.find(start):]
            result = max(result, substr)
            s = s[s.find(start)+1:]
        return result


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        c = max(s)

        i = s.find(c)
        r = i
        
        while i < len(s):
            
            if s[i] == c:
                if s[r:] < s[i:]:
                    r = i
                while i < len(s)-1 and s[i+1] == c:
                    i += 1
                    
            i += 1

        return s[r:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        left, right = 0, 0
        while right < len(s):
            if s[right] > s[left]:
                left = right
            elif s[right] == s[left]:
                if s[left: right] < s[right: right + right-left]:
                    left = right
                    
            right += 1
        
        return s[left: right+1]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = max(i + k + 1, j)
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        c = max(s)
        
        #a = []
        r = None
        i = 0
        while i < len(s):
            
            if s[i] == c:
                if r == None:
                    r = i
                else:
                    if s[r:] < s[i:]:
                        r = i
                #a.append(i)
                while i < len(s)-1 and s[i+1] == c:
                    i += 1
                    
            i += 1
            
        #r = a[0]
        #for i in a[1:]:
        #    if s[r:] < s[i:]:
        #        r = i
                
        return s[r:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_ord = 0
        if s.count(s[0])==len(s):
            return s
        for i in range(len(s)):
            max_ord = max(max_ord, ord(s[i]))
        start = chr(max_ord)
        result = ''
        for i in range(s.count(start)):
            substr = s[s.find(start):]
            result = max(result, substr)
            s = s[s.find(start)+1:]
            
        return result

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i,j,k = 0,1,0
        while j + k < n:
            if s[i:i+k+1] == s[j:j+k+1]:
                k += 1
            elif s[i:i+k+1] < s[j:j+k+1]:
                i = j
                k = 0
                j = j + 1
            else:
                j += k + 1
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        mc = ''
        mi = []
        
        for i in range(len(s)):
            if s[i] >= mc:
                mi.append(i)
                mc = s[i]
                
        ms = ''
        for i in mi:
            if s[i:] > ms:
                ms = s[i:]
        return ms
        
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        # c = s[0]
        # for num in range(len(s)):
        #     if s[num] > c:
        #         i = num
        #         c = s[num]
        j = i + 1
        k = 0
        
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
            elif s[i+k] > s[j+k]:
                j += k + 1
                k = 0
            else:
                i += k + 1
                j = i + 1
                k = 0
                
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # first store all the max chars in an array
        max_char = 'a'
        chars = []
        for i, char in enumerate(s):
            if char >= max_char:
                max_char = char
                chars.append(i)
        
        max_string = ''
        # now build the max substring from the chars array
        for idx in chars:
            if s[idx:] > max_string:
                max_string = s[idx:]
        return max_string

class Solution:
    def lastSubstring(self, s: str) -> str:
        maxIndex = []
        maxS = ''
        for i in range(len(s)):
            if(maxS < s[i]):
                maxS = s[i]
                maxIndex = []
                maxIndex.append(i)
            elif(maxS == s[i]):
                maxIndex.append(i)
            
        
        soln = s[maxIndex[0]:]
        for index in maxIndex:
            if(soln <= s[index:]):
                soln = s[index:]
                  
    
        return soln

class Solution:
    def lastSubstring(self, s: str) -> str:
        maxChar = max(s)
        
        indx = []
        
        for i in range(0, len(s)):
            if s[i] == maxChar and (i ==0 or s[i-1]!=maxChar):
                indx.append(i)
                
        
        maxind = indx[0]
        
        for i in range (1, len(indx)):
            step = 0
            curind = indx[i]
            while curind+step<len(s):
                
                if s[curind+step]>s[maxind+step]:
                    maxind = curind
                elif s[curind+step] == s[maxind+step]:
                    step+=1
                else:
                    break
                    
        return s[maxind:]


'''
case 1:
   a b ...
   i j    => change i to j , j to j+1
case 2:
    cbacbd
    i  j => i==j compare next one
    c b   a  c  b   d
    i i+1    j  j+1  => i==j compare next one
    i=2 < j+2
    i = j 
    j = new_i+1 why? allelemnts are smaller than original i 

'''
class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0,1,0
        while j+k < len(s):
            if s[i+k] > s[j+k]:
                j = j+k+1
                k = 0
            elif s[i+k] == s[j+k]:
                k += 1
            else:
                i = j #max(i + k + 1, j)
                j = i+1
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        last_c=max(s)
        last_str=s
        for i in range(len(s)):
            if s[i]==last_c and s[i:]>last_str:
                last_str=s[i:]
        return last_str


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        mx = max(s)
        
        prev = ''
        
        for i in range(len(s)):
            
            if s[i] == mx:
                if s[i:] > prev:
                    prev = s[i:]
                    
        return prev

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        c = max(s)
        
        a = []
        
        i = 0
        while i < len(s):
            
            if s[i] == c:
                a.append(i)
                while i < len(s)-1 and s[i+1] == c:
                    i += 1
                    
            i += 1
            
        r = a[0]
        for i in a[1:]:
            if s[r:] < s[i:]:
                r = i
                
        return s[r:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        char_list = set(list(s))
        char_list = list(char_list)
        char_list.sort()
        char = char_list[-1]
        res = char
        for i,c in enumerate(s):
            if c == char:
                if res < s[i:]:
                    res = s[i:]
        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = j
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        mxm = s[:]
        for i in range(len(s)):
            if s[i] >= mxm[0]:
                if s[i:] > mxm:
                    mxm = s[i:]
        return mxm

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_char = 'a'
        for char in s:
            if char > max_char:
                max_char = char
        
        compare = set()
        ret = max_char
        for i in range(len(s)):
            if s[i] == max_char:
                if s[i:] > ret:
                    ret = s[i:]
        
        return ret

class Solution:
    def lastSubstring(self, s: str) -> str:
        ans = ''
        c = max(s)
        idx = [i for i in range(len(s)) if s[i] == c]
        for i in idx:
            ans = max(ans, s[i:])
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_ = max(s)
        max_positions = [i for i, c in enumerate(s) if c == max_]
        return max(s[i:] for i in max_positions)


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        c = max(set(s))
        
        res = ''
        
        for i,x in enumerate(s):
            if x == c:
                res = max(res, s[i:])
        return res


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxIndex = []
        maxS = ''
        for i in range(len(s)):
            if(maxS < s[i]):
                maxS = s[i]
        for i in range(len(s)):
            if(maxS == s[i]):
                maxIndex.append(i)
        
        soln = s[maxIndex[0]:]
        for index in maxIndex:
            if(soln <= s[index:]):
                soln = s[index:]
                  
    
        return soln



class Solution:

    def lastSubstring(self, s: str) -> str:

        start_char = 'a'
        ans = 'a'

        for i in range(len(s)):
            
            if s[i] > start_char:
                start_char = s[i]

        for i in range(len(s)):

            if s[i] == start_char:
                ans = max(ans, s[i:])


        return ans




class Solution:

    def lastSubstring(self, s: str) -> str:

        start_char = 'a'
        ans = 'a'

        for i in range(len(s)):
            if s[i] > start_char:
                start_char = s[i]
                ans = s[i:]

            elif s[i] == start_char:

                ans = max(ans, s[i:])

        return ans


class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,k = 0,1,0
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = max(i + k + 1, j)
                j = i + 1
            k = 0
        return s[i:]

from collections import defaultdict

class Solution:       
    def lastSubstring(self, s: str) -> str:
        max_char = max(s)
        return max(s[i:] for i, c in enumerate(s) if c == max_char)



class Solution:
    def lastSubstring(self, s: str) -> str:
        
        biggest = max(s)
        start_ids = []
        
        for i, letter in enumerate(s):
            if letter == biggest: 
                start_ids.append(i)
        
        ans = s
        

        for i in start_ids:
            ans = max(ans, s[i::])
        
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_a = max(s)
        sub = s
        for i in range(len(s)):
            if s[i] == max_a:
                if s[i:] > sub:
                    sub = s[i:]
        return sub


class Solution:
    def lastSubstring(self, s: str) -> str:
        max_char = 'a'
        curr_idx = []
        for i in range(len(s)):
            if s[i] > max_char:
                curr_idx = [i]
                max_char = s[i]
            elif s[i] == max_char:
                curr_idx.append(i)
        
        curr_max = ''
        for idx in curr_idx:
            if s[idx:] > curr_max:
                curr_max = s[idx:]
        
        return curr_max

class Solution:       
    def lastSubstring(self, s: str) -> str:
        max_char = max(s)
        return max(s[i:] for i, c in enumerate(s) if c == max_char)


class Solution:
    def lastSubstring(self, s: str) -> str:
        st=set()
        
        for l in s:
            st.add(l)
        
        if len(st)==1:
            return s
            
        largest_letter = sorted(list(st))[-1]
        
        nums=[]
        for index,letter in enumerate(s):
            if letter==largest_letter:
                nums.append(index)
        
        rez=s[nums[0]:]
        og_first=nums[0]
        
        for i in nums[1:]:
            first = og_first
            second,j = i,i
            while second<len(s):
                if s[first]==s[second]:
                    first+=1
                    second+=1
                elif s[first]>s[second]:
                    break
                elif s[first]<s[second]:
                    rez=s[j:]
                    og_first=j
                    break
        
        return rez
        
                
        
        
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        l=[]
        least='a'
        index=[]
        for i,el in enumerate(s):
            if el==least:
                index.append(i)
            elif el>least:
                index=[i]
                least=el
        ans=''
        for i in index:
            ans=max(ans,s[i:])
        return ans

from collections import defaultdict

class Solution:       
    def lastSubstring(self, s: str) -> str:
        all_strings = set()
        max_char = None
        char_to_idx = defaultdict(lambda: [])
        
        for i, c in enumerate(s):
            if max_char == None or c > max_char:
                max_char = c
            char_to_idx[c].append(i)
        
        max_string = None
        for start_idx in char_to_idx[max_char]:
            # for j in range(start_idx+1, len(s)+1):
            new_string = s[start_idx:]
            if max_string == None or new_string > max_string:
                max_string = new_string
        
        return max_string




class Solution:

    def lastSubstring(self, s: str) -> str:


        start_char = max(s)
        ans = start_char


        # for i in range(len(s)):
        #     if s[i] > start_char:
        #         start_char = s[i]

        for i in range(len(s)):
            if s[i] == start_char:
                ans = max(ans, s[i:])


        return ans




class Solution:

    def lastSubstring(self, s: str) -> str:

        start_char = 'a'
        ans = 'a'

        for i in range(len(s)):
            
            if s[i] > start_char:
                start_char = s[i]
                ans = s[i:]

        for i in range(len(s)):

            if s[i] == start_char:
                ans = max(ans, s[i:])


        return ans


class Solution:
    def lastSubstring(self, s: str) -> str:
        ans = s[0]
        for i in range(len(s)):
            if s[i]<ans[0]:
                continue
            else:
                
            # for j in range(i, len(s)):
            #     if s[i:j+1]>ans:
                ans = max(s[i:], ans)
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
    
        max_letter = max(s)
        
        curr_max_index = s.find(max_letter)
        curr_substring = s[curr_max_index:]
        
        output = s
        
        next_max_index = 0
        
        while (True):
            next_max_index = s.find(max_letter, curr_max_index + 1)
            if next_max_index == -1:
                return max(curr_substring, output)
            
            if curr_substring > output:
                output = curr_substring
            
            curr_max_index = next_max_index
            curr_substring = s[curr_max_index:]

        


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxChar = s[0]
        
        for c in s:
            maxChar = max(maxChar, c)
            
        print(maxChar)
        
        check = ''
        
        for i in range(0, len(s)):
            if s[i] == maxChar and s[i:] > check:
                check = s[i:]
        
        return check
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        m, i, k =0,1,0 #m:maxbeginwith, i:possible candidate after m, l: current length
        while i+k< len(s):
            if s[m+k] ==s[i+k]:
                k+=1
            elif s[m+k] >s[i+k]:
                i = i+k+1
                k=0
            else:
                m = max(m+k+1,i)
                i=m+1
                k=0
        return s[m:]

from collections import defaultdict

class Solution:       
    def lastSubstring(self, s: str) -> str:
        max_char = None
        max_char_idx_all = set()
        max_string = None

        for i, c in enumerate(s):
            if max_char == None or c >= max_char:
                max_char = c
                new_string = s[i:]
                
                if max_string == None or new_string > max_string:
                    max_string = new_string            
        
        return max_string


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxChar = s[0]
        
        for c in s:
            maxChar = max(maxChar, c)
                    
        check = ''
        
        for i in range(0, len(s)):
            if s[i] == maxChar and s[i:] > check:
                check = s[i:]
        
        return check
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        aMax = max(a for a in s)
        inds = [i for i in range(len(s)) if s[i] == aMax]
        sMax = ''
        for i in inds:
            sMax = max(sMax,s[i:])
            # print(sMax, inds)
        return sMax


class Solution:
    def lastSubstring(self, s: str) -> str:
        mx = max(s)
        mxelement = [i for i, j in enumerate(s) if j == mx]
        mxstring = ''
        for i in mxelement:
            mxstring = max(s[i:], mxstring)
        return mxstring

class Solution:
    def lastSubstring(self, s: str) -> str:
        old = list(s)
        chars = list(s)
        chars.sort()
        index = old.index(chars[-1])
        indices = [i for i, x in enumerate(old) if x == chars[-1]]
        Max = s[indices[0]:]
        for i in range(len(indices)):
            Max = max(Max,s[indices[i]:])
        return Max
            


class Solution:    
    def lastSubstring(self, s: str) -> str:
        charInd = collections.defaultdict(list)
        # head = {}
        for i in range(len(s)):
            charInd[s[i]].append(i)        
        maxChr = max(charInd.keys())
        
        if len(charInd[maxChr]) == len(s)-1:
            return s
        
        m = s[-1]
        for i in charInd[maxChr]:
            m = max(m, s[i:])
        return m
            
            
            
            # node = head
#             for c in s[i:]:
#                 if c not in node:
#                     node[c] = {}
#                 node = node[c]
            
#         res = \"\"
#         node = head
#         while node:
#             ch = max(node.keys())
#             res += ch
#             node = node[ch]           
        
#         return res


class Solution:
    def lastSubstring(self, s: str) -> str:
    
        max_letter = max(s)
        
        curr_max_index = s.find(max_letter)
        curr_substring = s[curr_max_index:]
        
        output = s
        
        next_max_index = 0
        
        while (next_max_index != -1):
            next_max_index = s.find(max_letter, curr_max_index + 1)
            
            if curr_substring > output:
                output = curr_substring
            
            curr_max_index = next_max_index
            curr_substring = s[curr_max_index:]
            
        
        return output
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        # starts with max(ord(char)) should be start
        # longer substrings dominate
        i,j,k = 0,1,0
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = max(i + k + 1, j)
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        first = {}
        for i, letter in enumerate(s):
            if letter not in first: first[letter] = [i]
            else: first[letter].append(i)
        first_letter = max(first.keys())
        res = first_letter
        for idx in first[first_letter]:
            res = max(res, s[idx:])
        return res
            
        


from collections import defaultdict

class Solution:       
    def lastSubstring(self, s: str) -> str:
        max_char = max(s)
        max_string = None

        for i, c in enumerate(s):
            if c == max_char:
                new_string = s[i:]
                
                if max_string == None or new_string > max_string:
                    max_string = new_string            
        
        return max_string


class Solution:
    def lastSubstring(self, s: str) -> str:
        length, last, max_char = len(s), s[-1], s[-1]
        for i in range(length - 2, -1, -1):
            if s[i] < max_char:
                pass
            elif s[i] > max_char:
                last = s[i:]
                max_char = s[i]
            else:
                last = max(last,s[i:])
        return last


class Solution:

    def lastSubstring(self, s: str) -> str:

        start_char = 'a'
        ans = 'a'

        for i in range(len(s)):
            if s[i] > start_char:
                start_char = s[i]
                ans = s[i:]

            elif s[i] == start_char:

                ans = max(ans, s[i:])

        return ans


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        ind = collections.defaultdict(list)
        for i in range(len(s)):
            ind[s[i]].append(i)
        
        maxy = max(ind)
        
        ans = ''
        off = 0
        for i in ind[maxy]:
            s = s[i-off:]
            off+=(i-off)
            # print(s, off)
            ans = max(ans, s)
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        maxLet = ord(s[0])

        for c in s:
            maxLet = max(maxLet, ord(c))
        
        maxLet = chr(maxLet)
        mx = s
        for i,c in enumerate(s):
            if c == maxLet:
                mx = max(mx,s[i:])
                
        return mx

class Solution:
    def lastSubstring(self, s: str) -> str:
        slow, fast, length = 0, 1, 0
        while fast + length < len(s):
            if s[slow+length] == s[fast+length]: #if equal, compare the next character
                length += 1
            elif s[slow+length] > s[fast+length]: #the slow character is higher than fast one, compare the next first character
                fast += (length + 1)
                length = 0
            else: #the fast character is higher than slow one, compare the next sub string
                slow = fast
                fast = slow + 1
                length = 0

        return s[slow:]


import numpy as np
class Solution:
    def lastSubstring(self, s: str) -> str:
        
        input_list= np.array([ord(x) for x in s])
        i, = np.where(input_list == np.max(input_list))

        
        r = ''
        # M = max(s)
        for e in i:
            r = max(r, s[e:])
        
        return r


class Solution:
    def lastSubstring(self, s: str) -> str:
        length = len(s)
        last = s[-1]
        max_char = s[-1]
        for i in range(length - 2, -1, -1):
            if s[i] < max_char:
                pass
            elif s[i] > max_char:
                last = s[i:]
                max_char = s[i]
            else:
                last = max(last,s[i:])
        return last


class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s:
            return ''
        m=s[0]
        
        for i in range(1,len(s)):
            m=max(m,s[i])
            
        x=''
        
        for i in range(len(s)):
            if s[i]==m:
                x=max(x,s[i:])
        return x
    
        '''
        if len(x)==1:
            return s[x[0]:]
        #print(x)
        
        
        
        while len(x)>1:
            c=1
            m=s[x[0]+c]
            i=0
            while i<len(x):
                #print(x,m)
                if x[i]+c>=len(s):
                    if len(x)>1:
                        x.pop()
                        break
                    else:
                        return s[x[0]:]
                if s[x[i]+c]<m:
                    del x[i]
                    continue
                if s[x[i]+c]>m:
                    m=s[x[i]+c]
                    x=x[i:]
                    i=0
                    continue
                i+=1
            c+=1
        if x:
            return s[x[0]:]
        
        return ''
        '''

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        length = len(s)
        
        maxChar = ''
        maxCharIdxs = []
        
        for i in range(length):    
            maxChar = max(s[i], maxChar)
        
        for idx, char in enumerate(s):
            if char == maxChar:
                maxCharIdxs.append(idx)
        
        maxSubstr = ''
        for maxIdx in maxCharIdxs:
            maxSubstr = max(s[maxIdx: ], maxSubstr)
        
        return maxSubstr
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        def helper(s):
            p1, p2, prev_max_string = 0, -1, None
            for i, l in enumerate(s): 
                if p2 > 0: 
                    # has valid start
                    if ord(l) > ord(s[p1 + i-p2]): 
                        p1 = p2

                    elif ord(l) == ord(s[p1 + i-p2]): 
                        pass
                    else: 
                        p2 = -1                
                else:
                    # how you initialize the string
                    if ord(l) > ord(s[p1]): 
                        p1 = i
                    elif ord(l) < ord(s[p1]): 
                        pass
                    else: 
                        p2 = i
            return s[p1:]
        
        ans = helper(s)
        while len(s) > len(ans): 
            s, ans = ans, helper(ans)
        return s
    
                
                
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        index = {c: i for i, c in enumerate(sorted(set(s)))}
        radix, val, cur, lo = len(index), 0, 0, 0
        for i in range(len(s) - 1, -1, -1):
            cur = index[s[i]] + cur / radix
            if cur >= val:
                lo, val = i, cur
        return s[lo:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s:
            return s
        first, second, runner = 0, 1, 0
        while second + runner < len(s):
            if s[first + runner] == s[second + runner]:
                runner += 1
            elif s[first + runner] > s[second + runner]:
                second = second + runner + 1
                runner = 0
            else:
                if s[second + runner] > s[first]:
                    first, second, runner = second + runner, second + runner + 1, 0
                else:
                    first, second, runner = second, second + 1, 0
            # print(first, second, runner)
            
        return s[first:]
                


class Solution:
    def lastSubstring(self, s: str) -> str:
        l = len(s)
        # take all substring which goes on till the end.
        # make l substrings.
        # find the largest lowercase english letter
        all_chars = set(list(s))
        all_chars = list(all_chars)
        all_chars.sort()
        mychar = all_chars[-1]
        max_sub = mychar
        for i, c in enumerate(s):
            if c == mychar:
                candidate = s[i:]
                if max_sub < candidate:
                    max_sub = candidate
                    
        return max_sub

class Solution:
    def lastSubstring(self, s: str) -> str:

        if not s:
            return ''
        
        maxval = s
        maxstart = s[0]
        
        for i in range(len(s)):
            if s[i] >= maxstart and s[i:] > maxval:
                maxstart = s[i]
                maxval = s[i:]

                
        return maxval

class Solution:
    def lastSubstring(self, s: str) -> str:
        # create substrings, sort lexicographically?
        prev=s[0]
        max_store=[]
        # O(n)
        max_s=max(s)
        for i in range(len(s)):
            if s[i]==max_s:
                if s[i:]>prev:
                    prev=s[i:]
                
        # for i in range(len(s)):
        #     if s[i:]>prev:
        #         prev=s[i:]
        return prev

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 1-1
        j = 1
        large = s[i]
        while(j < len(s)):
            if (s[j] > large):
                i = j
                large = str(s[j])
            else:
                large += s[j]
            j += 1
        i = 1
        print(large)
        res = large
        while(i < len(large)):
            if (large[i-1] == res[1-1]):
                if (large[i-1:] > res):
                    res = large[i-1:]
                    # print(res)
            i += 1
        return res


class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s:
            return s
        max_char = s[0]
        for c in s:
            if c > max_char:
                max_char = c
                
        largest = s
        cur, prev = 0, 0
        for i in range(len(s)):
            if s[i] == max_char:
                #print(i, s[i], s[cur:i+1])
                if cur and s[cur:] > largest:
                    largest = s[cur:]
                cur = i
                                
        if cur and s[cur:] > largest:
            largest = s[cur:]
        
        return largest

class Solution:
    def lastSubstring(self, s: str) -> str:
        if len(set(s))==1:
            return s
        alpha=sorted(list(set(s)))
        start=alpha[-1]
        
        n=len(s)
        index=[]
        for i,char in enumerate(s):
            if char==start:
                index.append(i)
            
        prefix=start
        maxprefix=start
        while index:
            nextindex=[]
            for i in index:
                if i+1<n:
                    if prefix+s[i+1]==maxprefix:
                        maxprefix=prefix+s[i+1]
                        nextindex.append(i+1)
                    elif prefix+s[i+1]>maxprefix:
                        maxprefix=prefix+s[i+1]
                        nextindex=[i+1]
            prefix=maxprefix
            index=nextindex
        
        return maxprefix
                    


class Solution:
    def lastSubstring(self, s: str) -> str:
        if len(s) == 1:
            return s
        
        start, end, length = 0, 1, 0
        
        while end + length < len(s):
            if s[start + length] == s[end + length]:
                length += 1
            elif s[start + length] > s[end + length]:
                end += length + 1
                length = 0
            else:
                start = end
                end = start + 1
                length = 0
        
        return s[start:]
                


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        bestStr = s
        bestChar = s[0]
        for i in range(1, len(s)):
            if s[i] >= bestChar and s[i:] > bestStr:
                bestChar = s[i]
                bestStr = s[i:]
                
                
        return bestStr


class Solution:
    def lastSubstring(self, s: str) -> str:
        mx = max(s)
        mxelement = [i for i, j in enumerate(s) if j == mx]
        mxstring = ''
        for i in mxelement:
            if s[i:]>mxstring:
                mxstring = s[i:]
        return mxstring

class Solution:
    def lastSubstring(self, s: str) -> str:
        c = max(set(s))
        res = ''
        for i,x in enumerate(s):
            if x == c:
                res = max(res, s[i:])
        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        largest_character = max(set(s))
        result = ''
        
        for i, char in enumerate(s):
            
            if char==largest_character:
                result = max(result,s[i:])
                
        return result


class Solution:
    def lastSubstring(self, s: str) -> str:
        res = s
        maxChar = max(s)
        for i in range(1, len(s)):
            if s[i] == maxChar and s[i:] > res:
                res = s[i:]
        
        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        # create substrings, sort lexicographically?
        prev=s[0]
        max_store=[]
        # O(n)
        max_s=max(s)
        for i in range(len(s)):
            if s[i]==max_s:
                if s[i:]>prev:
                    prev=s[i:]
                

        return prev

class Solution:
    def lastSubstring(self, s: str) -> str:
        if len(set(s))==1: return s
        x=max(s)
        n=len(s)
        res=[]
        for i in range(n-1,-1,-1):
            if res and s[i]==x:
                k=0
                while k<len(res[-1]) and res[-1][k]==s[i+k]:
                    k+=1
                if k<len(res[-1]) and res[-1][k]<s[i+k]:
                    res[-1]=s[i:]
                elif k==len(res[-1]):
                    res[-1]=s[i:]
            elif s[i]==x:
                res.append(s[i:])
        return res[-1]
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        c = max(s)
        maxSub = ''
        loc = s.find(c, 0)
        while loc != -1:
            maxSub = max(maxSub, s[loc:])
            loc = s.find(c, loc + 1)
        return maxSub


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxchr = max(s)
        index = []
        maxstring = ''
        i = 0
        while i < len(s) and s[i:].find(maxchr) != -1:
            if i == 0 or s[i] != s[i-1]:
                temp = s[i:].index(maxchr) + i
                index.append(temp)
                maxstring = max(maxstring, s[temp:])
                i = temp+1
            else:
                i += 1
        return maxstring

class Solution:
    def lastSubstring(self, s: str) -> str:
        def helper(s, start = 0):
            p1, p2 = start, -1
            # for i, l in enumerate(s): 
            for i in range(start+1, len(s)): 
                l = s[i]
                if p2 > 0: 
                    # has valid start
                    if ord(l) > ord(s[p1 + i-p2]): 
                        p1 = p2

                    elif ord(l) == ord(s[p1 + i-p2]): 
                        pass
                    else: 
                        p2 = -1                
                else:
                    # how you initialize the string
                    if ord(l) > ord(s[p1]): 
                        p1 = i
                    elif ord(l) < ord(s[p1]): 
                        pass
                    else: 
                        p2 = i
            # return s[p1:]
            return p1
        
        i, j = 0, helper(s, 0)
        while j > i: 
            i, j = j, helper(s, j)
        return s[j:]
        
        # ans = helper(s, 0)
        # while len(s) > len(ans): 
        #     s, ans = ans, helper(ans)
        # return ans
        
        
        


class Solution:
    def lastSubstring(self, s: str) -> str:

        input_string = s
        
    
        max_letter = max(input_string)
        
        curr_max_index = input_string.find(max_letter)
        curr_substring = input_string[curr_max_index:]
        
        output = input_string
        
        next_max_index = 0
        
        while (True):
            next_max_index = input_string.find(max_letter, curr_max_index + 1)
            if next_max_index == -1:
                return max(curr_substring, output)
            
            if curr_substring > output:
                output = curr_substring
            
            curr_max_index = next_max_index
            curr_substring = input_string[curr_max_index:]
            
            if output > curr_substring:
                continue
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)
        z = max(d.keys())                   # max char
        ids = d[z]                                # start pos for substrings
        return max(s[start:] for start in ids)

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i = n - 2
        last = n - 1
        while i >= 0:
            if s[i] > s[last]:
                last = i 
                i -= 1
                continue
            if s[i] < s[last]:
                i -= 1
                continue
            j = 1
            while True:
                tempi = i + j
                templast = last + j
                if templast >= n:
                    last = i
                    i -= 1
                    break
                if tempi == last:
                    last = i
                    i -= 1
                    break
                if s[tempi] > s[templast]:
                    last = i
                    i -= 1
                    break
                if s[tempi] < s[templast]:
                    i -= 1
                    break
                j += 1
        return s[last:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        for i,c in enumerate(s):
            if i == 0:
                max_c = c
                max_id=[i]
            else:
                if c > max_c:
                    max_id = [i]
                    max_c = c
                elif c == max_c:
                    max_id.append(i)
        max_substr = s[max_id[0]:]
        for idx in max_id:
            if s[idx:] > max_substr:
                max_substr = s[idx:]
        return max_substr


class Solution:
    def lastSubstring(self, s: str) -> str:
    
        max_letter = max(s)
        
        curr_max_index = s.find(max_letter)
        curr_substring = s[curr_max_index:]
        
        output = s
        
        next_max_index = 0
        
        while (True):
            next_max_index = s.find(max_letter, curr_max_index + 1)
            if next_max_index == -1:
                return max(curr_substring, output)
            
            if curr_substring > output:
                output = curr_substring
            
            curr_max_index = next_max_index
            curr_substring = s[curr_max_index:]
            
            if output > curr_substring:
                continue
        


class Solution:
    def lastSubstring(self, s: str) -> str:

        char_max = max(s)
        ind = s.find(char_max)
        s=s[ind:]
        n = len(s)
        arr = [0]*n
        arr[-1]=s[-1]
        ans=arr[-1]
        for i in range (n-2,-1,-1):
            if s[i]==char_max:
                if s[i:]>ans:
                    ans=s[i:]
        return ans

class Node:
    def __init__(self, val=None, is_end=False, children=None):
        self.val = val
        self.children = children if children else {}

class Solution:
    def add_suffix(self, root: Node, s: str):
        for c in s:
            if c not in root.children:
                root.children[c] = Node(val=c)
            root = root.children[c]
        
    def get_last_substring(self, root: Node):
        if not root.children:
            return [root.val]
        return [root.val] + self.get_last_substring(max(root.children.items())[1])
            
    
    def lastSubstring(self, s: str) -> str:
        c = max(s)
        res = ''
        for i,x in enumerate(s):
            if x == c:
                res = max(res, s[i:])
        return res
        # root = Node('')
        # for i in range(len(s)):
        #     self.add_suffix(root, s[i:])
        # return ''.join(self.get_last_substring(root))


class Solution:
    def lastSubstring(self, s: str) -> str:
        char_list = set(list(s))
        char_list = list(char_list)
        char_list.sort()
        last_char = char_list[-1]
        max_string = last_char
        for index, char in enumerate(s):
            if char == last_char and max_string < s[index:]:
                max_string = s[index:]
        return max_string
    


class Solution:
    def lastSubstring(self, s: str) -> str:
        s_len, left, right, step = len(s), 0, 1, 0
        while(right + step < s_len):
            if s[right + step] > s[left + step]:
                left, right, step = right , right+1, 0
            elif s[right + step] < s[left + step]:
                right, step = right+step+1, 0
            else:
                step += 1
        return s[left:]



class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        
        maxLetter = max(s)
        maxSubstring = None
        
        for i, letter in enumerate(s):
            if letter == maxLetter:
                if not maxSubstring or s[i:n] > maxSubstring:
                    maxSubstring = s[i:n]
        
        return maxSubstring


class Solution:
    def lastSubstring(self, s: str) -> str:
        char_max = max(s)
        ind = s.find(char_max)
        s=s[ind:]
        n = len(s)
        arr = [0]*n
        arr[-1]=s[-1]
        ans=arr[-1]
        i=n-2
        while i>-1:
        # for i in range (n-2,-1,-1):
            if s[i]==char_max:
                if s[i:]>ans:
                    ans=s[i:]
            i-=1
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        char_max = max(s)
        ind = s.find(char_max)
        s=s[ind:]
        n = len(s)
        arr = [0]*n
        arr[-1]=s[-1]
        ans=arr[-1]
        i=n-2
        while i>-1:
            if s[i]==char_max:
                if s[i:]>ans:
                    ans=s[i:]
            i-=1
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        mx = max(s)
        pos = [i for i in range(len(s)) if s[i] == mx]
        return max(s[i:] for i in pos)

import numpy as np

class Solution:
    def lastSubstring(self, s: str) -> str:
        mx = max(s)
        #mxelement = [i for i, j in enumerate(s) if j == mx]
        
        
        values = np.array(list(s))
        mxelement = np.where(values == mx)[0]

        
        mxstring = ''
        for i in mxelement:
            if s[i:]>mxstring:
                mxstring = s[i:]
        return mxstring

class Solution:
    def lastSubstring(self, s: str) -> str:
        largest_character = max(set(s))
        result = ''
        ind = [i for i,char in enumerate(s) if char==largest_character]
        
        #for i, char in enumerate(s):
        for i in ind:
            
            #if char==largest_character:
            result = max(result,s[i:])
                
        return result


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j = 0, 1
        k = 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] > s[j + k]:
                j += k + 1
                k = 0
            else:
                i = j
                j = i + 1
                k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        maximum = s
        for i in range(1,len(s)):
            if s[i:]>maximum:
                maximum = s[i:]
                
        return maximum        


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        res = s

        for i in range(1, len(s)):
            if s[i::] > res:
                res = s[i::]
        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        dicmap = {}
        maxhold =s[0]
        index = 0
    
        for i in range(0,len(s)):
            if s[i:] > maxhold:
                maxhold = s[i:]
                index = i

                
            
        
    

                
        
        return s[index:]
                
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        max = s
        for i in range(len(s)):
            if max<s[i:]:
                max=s[i:]
        return max
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        maxs = None
        for sidx in range(len(s)):
            if maxs == None or s[sidx: ] > maxs:
                maxs = s[sidx: ]
        return maxs

class Solution:    #双指针
    def lastSubstring(self, s: str) -> str:
        left=0    ## 代表以left为起始点的字串
        right=1  
        step=0
        while (right+step)<len(s):
            if s[left+step]<s[right+step]:
                left=right
                right+=1
                step=0
            elif s[left+step] == s[right+step]:
                step+=1
            else:
                right+=step+1
                step=0
        return s[left:]
                
                
##使用指针left记录当前最大的后缀子串的起始坐标。 指针right用来遍历。 一开始left = 0， right = 1，从左往右遍历。
##当str[left] 小于 str[right], 则以left开头的后缀子串一定小于以right开头的后缀子串，所以left = right， right+1
##当str[left] 大于 str[right], 则left不动，right+1
##当str[left] 等于 str[right]， 则比较str[left + k], str[right + k], k = 1、2、3...。 直到出现不相等，否则一直比较直到结束。
##当str[left + k] 小于 str[right + k]， left = right, right+1
##当str[left + k] 大于于 str[right + k]， left不动, right+step+1。



class Solution:
    def lastSubstring(self, s: str) -> str:
        return max(s[i:] for i in range(len(s)))

class Solution:
    def lastSubstring(self, s: str) -> str:
        maxStr = s
        for i in range(1, len(s)):
            if s[i:] > maxStr:
                maxStr = s[i:]
                
        return maxStr

class Solution:
    def lastSubstring(self, s: str) -> str:
        lastSubstring = s
        for i in range(1, len(s)):
            if s[i:] > lastSubstring:
                lastSubstring = s[i:]
        return lastSubstring

class Solution:

    def lastSubstring(self,s: str) -> str:
        result = s
        for i in range(len(s)):
            if s[i:]>result:
                result = s[i:]
        return result


class Solution:
    def lastSubstring(self, s: str) -> str:
        if len(s) == 1:
            return s
        res = s
        for i in range(1,len(s)):
            if s[i:] > res:
                res = s[i:]
        return res
            
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        
        
        l  = 0
        r  = len(s)
        max_s = s
        
        while l < r:
            
            if s[l:r] >= max_s:
                max_s = s[l:r]
            
            l += 1
            
            
        return max_s

class Solution:
    def lastSubstring(self, s: str) -> str:
        # 因为字典顺序，可以看出 ab abc 两个字符中， abc 更大，因为两个字符相同时，谁更长谁order 更大
        # 所以，可以确定我们只需要找到 最大substring 的起始点，然后把前面都切掉，后缀就是答案
        # 利用双指针来找起始点
        # i j 两个指针 指向数组的两个字符，维持 i +k ， j +k 两个substring
        # 每次比较，如果i 的更大，那么j就要更新到j + k + 1， 因为在j ～ j + k 之间的字符都是小于i的，不然也不会等到现在更新
        # 如果 j更大，那么用j的去更新i，j移动到自己下一个位置 找最大string，继续去比较
        i = 0
        j = 1
        k = 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
                continue
            elif s[i + k] > s[j + k]:
                j = j + k + 1
            else:
                i = j
                j = i + 1
            k = 0
        return s[i:]
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        ans = s
        for i in range(1, len(s)):
            ans = max(ans, s[i:])
        return ans

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s);
        cur = ord(s[0]);
        start = 0;
        end = 0
        i=1;
        while i<n:
            if cur > ord(s[i]):
                end+=1;
                i+=1;
            elif cur < ord(s[i]):
                start,end=i,i;
                cur = ord(s[i]);
                i+=1;
            else:
                k = start+1;
                prev= i;
                i+=1;
                while k<prev and i<n:
                    if ord(s[k]) > ord(s[i]):
                        end = i;
                        break;
                    elif ord(s[i]) > cur:
                        start,end = i,i;
                        cur = ord(s[i]);
                        break;
                    elif ord(s[k]) < ord(s[i]):
                        start = prev;
                        end = i;
                        break;
                    i+=1;
                    k+=1;
                if i==n:
                    end = n-1;
                if k==prev:
                    end = i;
        return s[start:end+1];

class Solution:       
    def lastSubstring(self, s: str) -> str:
#         curr_value = 0
#         max_value = 0
#         max_idx = None
#         char_to_id = {' ': 0}
#         char_to_id.update((c, i + 1) for i, c in enumerate(sorted(frozenset(s))))
#         radix = len(char_to_id) ** (len(s) - 1)
        
#         for i in range(len(s) - 1, -1, -1):
#             curr_value = char_to_id[s[i]] * radix + curr_value // len(char_to_id)

#             if curr_value > max_value:
#                 max_value = curr_value
#                 max_idx = i

#         return s[max_idx:]
        index = {c: i for i, c in enumerate(sorted(set(s)))}
        radix, val, cur, lo = len(index), 0, 0, 0
        for i in range(len(s) - 1, -1, -1):
            cur = index[s[i]] + cur / radix
            if cur >= val:
                lo, val = i, cur
        return s[lo:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,k = 0,1,0
        n = len(s)
        
        while(j+k < n):
            if s[i+k] == s[j+k]:
                k += 1
            elif s[i+k] < s[j+k]:
                i = j
                j += 1
                k = 0
            else:
                j += 1
                k = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        m = max(s)
        ans = ''
        for i in range(len(s)):
            ans = max(ans,s[i:])
        return ans
            
                
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        #a b c x a a x x b c d x d d a
        #      |     |         |
        
        start = 0
        for i in range(len(s)):
            if s[i] > s[start]:
                start = i
        
        candidates = set()
        length = 1
        
        for i in range(len(s)):
            if s[i] == s[start] and (i == 0 or s[i - 1] != s[start]):
                candidates.add(i)
        
        while len(candidates) > 1:
            need_remove = set()
            maxc = 'a'
            
            for candidate in candidates:
                end = candidate + length
                if end >= len(s):
                    need_remove.add(candidate)
                    continue
                
                c = s[end]
                if c > maxc:
                    maxc = c
            
            for candidate in candidates:
                end = candidate + length
                
                if end >= len(s):
                    continue
                if s[end] != maxc:
                    need_remove.add(candidate)
            
            if len(need_remove) >= len(candidates): break
            for idx in need_remove:
                candidates.discard(idx)
                
            length += 1
        
        res = ''
        for candidate in candidates:
            curt = s[candidate:]
            if curt > res:
                res = curt
        return res

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = 1
        k = 0
        n = len(s)
        
        
        while j + k < n:
          if s[i+k] == s[j+k]:
            k += 1
            continue
          elif s[i+k] > s[j+k]:
            j = j+k+1
          else:
            i = i+k+1
          if i==j:
            j = j+1
          k = 0
        
        return s[i:]
        
        


class Solution:
    
    ## Method 2 - Two Pointers
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = i+1
        result = s
        while j < len(s):
            if s[i] > s[j]:
                j += 1
                continue
            elif s[i] < s[j]:
                i = j
                j += 1
            else:
                
                step = 0
                while j+step < len(s) and s[i+step] == s[j+step]:
                    step += 1
                
                # print(j+step, len(s))
                if j+step == len(s):
                    return s[i:]
                if s[i+step] > s[j+step]:
                    j += 1
                    continue                
                else:
                    i = j
                    j += 1
                # print(s[i:], i, j)
                    
        return s[i:]
            
            
        
    
    
#     ## Method 1 - brute force (imroved)
#     def lastSubstring(self, s: str) -> str:
#         start = max(set(s))
#         result = \"\"
#         for i, char in enumerate(s):
#             # if i + len(result) > len(s):
#             #     break
#             if char == start:
#                 result = max(result, s[i:])
                
#         return result


class Solution:
    def lastSubstring(self, s: str) -> str:
        max_ord = max([ord(c) for c in s])
        max_ord_idxs = [i for i in range(len(s)) if ord(s[i]) == max_ord]
        first_unique_idx = [i for i in range(len(max_ord_idxs)-1, -1, -1) if i == 0 or max_ord_idxs[i]-1 != max_ord_idxs[i-1] ]
        max_ord_idxs = [max_ord_idxs[i] for i in first_unique_idx]
        if len(max_ord_idxs) == 1:
            return s[max_ord_idxs[0]:]
        
        def findNextMaxOrd(cur_idxs, level):
            nextOrd2CurIdx = collections.defaultdict(list)
            hist_max = float('-inf')
            for idx in cur_idxs:
                if idx < len(s) - level:
                    nextOrd2CurIdx[ord(s[idx+level])].append(idx)
                    hist_max = max(hist_max, ord(s[idx+level]))
            return nextOrd2CurIdx[hist_max]

        # Filtering indexes with maximum ord by comparing k-level away
        level = 1
        while 1:
            max_ord_idxs = findNextMaxOrd(max_ord_idxs, level)
            if len(max_ord_idxs) == 1:
                return s[max_ord_idxs[0]:]
            level += 1

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        # naive: O(n^2)
        # slight optimization to sort as we go 
#         last = s
#         for i in range(len(s)):
#             for j in range(i+1, len(s)+1):
#                 if s[i:j] > last:
#                     last = s[i:j]
                
#         return last
        
        # find positions of earliest letters in alphabet 
        # leastLetter = s[0]
        # positions = [0]
        # for i in range(1,len(s)):
        #     if s[i] > leastLetter:
        #         leastLetter = s[i]
        #         positions = [i]
        #     elif s[i] == leastLetter:
        #         positions.append(i)
        i, j, k = 0, 1, 0
        n = len(s)        
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
                i = i+k+1
            if i==j:
                j = j+1
            k = 0
        return s[i:]


# O(n) time and O(1) space
# The last substring starts with the max char, find the start point(max char), and check
# Finding just the index of max char(first or last occurence) will give us error in the following cases:
# \"cacacb\" -> \"cb\"
# \"abab\" -> \"bab\"
class Solution:
    def lastSubstring(self, s: str) -> str:        
        i, j = 0, 1
        ptr = 0
        
        while j+ptr < len(s):
            if s[i+ptr] == s[j+ptr]:
                ptr += 1
            elif s[i+ptr] < s[j+ptr]:
                i = j
                j += 1
                ptr = 0
            else:
                j += 1
                ptr = 0
                
        return s[i:]
    
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i+offset < len(s) and j+offset < len(s):
            if s[i+offset]==s[j+offset]:
                offset += 1
            else:
                if s[i+offset] < s[j+offset]:
                    i = j
                else:
                    j += offset+1
                if i==j:
                    j += 1
                offset = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        pool, c, repeat = [], max(set(s)), False    # c is the max char, pool contains the candidates
        for i,x in enumerate(s):
            if x == c:
                if not repeat:                      # only add non-repeat head (if there's some smaller char in between) 'zzzazz...', not add 'zzzzzz...'
                    pool.append(i)
                    repeat = True
            else:
                repeat = False
        k = 1
        while len(pool) > 1:                        # if there are more than one substring start with the head
            new_pool, c = [], ''
            for i in pool:
                sc = s[i+k] if i+k < n else ''      # continue to compare the second, third, ..., k-th char
                if sc > c:
                    new_pool = [i]
                    c = sc
                elif sc == c:
                    new_pool.append(i)
            pool = new_pool
            k += 1                                  # compare the next char
        return s[pool[0]:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        '''
        res=''
        for i in range(len(s)):
            res=max(s[i:],res)
        return res
        '''
        max_ord = max([ord(c) for c in s])
        max_ord_idxs = [i for i in range(len(s)) if ord(s[i]) == max_ord]
        first_unique_idx = [i for i in range(len(max_ord_idxs)-1, -1, -1) if i == 0 or max_ord_idxs[i]-1 != max_ord_idxs[i-1] ]
        max_ord_idxs = [max_ord_idxs[i] for i in first_unique_idx]
        if len(max_ord_idxs) == 1:
            return s[max_ord_idxs[0]:]
        
        def findNextMaxOrd(cur_idxs, level):
            nextOrd2CurIdx = collections.defaultdict(list)
            hist_max = float('-inf')
            for idx in cur_idxs:
                if idx < len(s) - level:
                    nextOrd2CurIdx[ord(s[idx+level])].append(idx)
                    hist_max = max(hist_max, ord(s[idx+level]))
            return nextOrd2CurIdx[hist_max]

        # Filtering indexes with maximum ord by comparing k-level away
        level = 1
        while 1:
            max_ord_idxs = findNextMaxOrd(max_ord_idxs, level)
            if len(max_ord_idxs) == 1:
                return s[max_ord_idxs[0]:]
            level += 1

class Solution:
    # idea is we have two sequences: i ...i+k and j ...j+k and differ only at s[i+k] and j[i+k]
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                # increase j value to get out of loop
                j = j + k + 1; 
            else: 
                # increase i value because we just found a starting letter that is bigger
                i = i + k +1; 
            if i == j: 
                j = j + 1 
            k = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        max = 0
        i = 1
        j = 0
        while i + j < len(s):
            if s[i + j] == s[max + j]:
                j = j + 1
            elif s[i + j] > s[max + j]:
                max = i
                j = 0
                i = i + 1
            else:
                j = 0
                i = i + 1

        return s[max:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        # Recursively find all with the largest lecsographical order,
        
        # when only one left => that is end of our substring
        
        # store start index and end index
        all_same = True
        first_char = s[0]
        for c in s:
            if first_char != c:
                all_same = False
        if all_same:
            return s
        
        max_char = max([c for c in s])
        indexes = [[i, i+1] for i, c in enumerate(s) if c == max_char]
        
        output = []
        
        def max_substring(indexes):
            if len(indexes) == 1:
                output.append(indexes[0])
                return
            
            nonlocal s
            max_char = max([s[indx[1]] for indx in indexes if indx[1] < len(s)])
            
            next_indexes = []
            for indx in indexes:
                if indx[1] < len(s) and s[indx[1]] == max_char:
                    indx[1] += 1
                    next_indexes.append(indx)
            max_substring(next_indexes)
        
        max_substring(indexes)
        return s[output[0][0]:]
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = i + k + 1
            if i == j:
                j += 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,k=0,1,0
        ans=0
        while j+k<len(s):
            if s[i+k]==s[j+k]:
                k+=1
            elif s[i+k]>s[j+k]:
                ans=i
                j=j+k+1
                k=0
            else:
                ans=j
                i=max(i+k+1, j)
                j=i+1
                k=0
        return s[ans:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s:
            return None
        
        # get max char from s
        max_char = max(s)
        max_idxs = []
        
        # get all max_char indexs to append into max_idxs
        for i in range(len(s)):
            if s[i] != max_char:
                continue
            if not max_idxs or s[i - 1] != max_char:
                max_idxs.append(i)
                
        # also append the length of s into the max_idxs for compersion
        max_idxs.append(len(s))
        
        # initialize the temp max letter
        max_letter = s[max_idxs[0]:max_idxs[1]]
        ans_idx = max_idxs[0]
        # using for loop to compare with each shrot letter those leading by max_char
        for i in range(len(max_idxs) - 1):
            cur = s[max_idxs[i]:max_idxs[i + 1]]
            print(cur)
            if max_letter < cur:
                max_letter = cur
                ans_idx = max_idxs[i]
                
        return s[ans_idx:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        index = {c: i for i, c in enumerate(sorted(set(s)))}
        cur, radix, max_val, max_i = 0, len(index), 0, 0
        for i in range(len(s)-1, -1, -1):
            cur = index[s[i]] + cur/radix
            if cur > max_val:
                max_val, max_i = cur, i
        return s[max_i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]: # if left is greater
                j = j + k + 1
            else: # if right is greater
                i = i + k + 1
            if(i == j):
                j = i + 1
            k = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        # start from s[i], s[j] (i=0,j=i+1)
        i = 0
        j = i + 1
        k = 0
        while j + k < len(s):
            if s[i + k] > s[j+k]:
                j += 1
                k = 0
                
            elif s[i+k] < s[j+k]:
                i = j
                j = i + 1
                k = 0
            else:
                
                k += 1
        return s[i:]


class Solution:
    
    def lastSubstring(self, s: str) -> str:
        begin = 0
        end = 1
        offset = 0
        while end + offset < len(s):
            # print(begin, end, offset,'\\t',s[begin+offset],s[end+offset],'\\t', -ord(s[begin+offset]) + ord(s[end+offset]),'\\t', s[begin:])
            if s[begin + offset] > s[end+offset]:
                offset = 0
                end += 1
            elif s[begin + offset] < s[end+offset]:
                begin = end
                end += 1
                offset = 0
            else:
                offset += 1
        return s[begin:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        max_ord = max([ord(c) for c in s])
        max_ord_idxs = [i for i in range(len(s)) if ord(s[i]) == max_ord]
        print(max_ord_idxs)
        first_unique_idx = [i for i in range(len(max_ord_idxs)-1, -1, -1) if i == 0 or max_ord_idxs[i]-1 != max_ord_idxs[i-1] ]
        print(first_unique_idx)
        max_ord_idxs = [max_ord_idxs[i] for i in first_unique_idx]
        
        def findNextMaxOrd(cur_idxs, level):
            nextOrd2CurIdx = collections.defaultdict(list)
            hist_max = float('-inf')
            for idx in cur_idxs:
                if idx < len(s) - level:
                    nextOrd2CurIdx[ord(s[idx+level])].append(idx)
                    hist_max = max(hist_max, ord(s[idx+level]))
            return nextOrd2CurIdx, hist_max

        level = 1
        while 1:
            if len(max_ord_idxs) == 1:
                return s[max_ord_idxs[0]:]
            
            nextOrd2CurIdx, hist_max = findNextMaxOrd(max_ord_idxs, level)
            
            if len(nextOrd2CurIdx[hist_max]) == 1:
                return s[nextOrd2CurIdx[hist_max][0]:]
            else:
                max_ord_idxs = nextOrd2CurIdx[hist_max]
                level += 1
                


class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i = j
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i :]

class Solution:
    # O(n^2) time, O(1) space
    def lastSubstring(self, s: str) -> str:
        best = 0
        n = len(s)
        for i in range(n):
            if s[i] > s[best]:
                best = i
            elif s[i] == s[best]:
                idx1, idx2 = best, i
                while idx2 < n and s[idx1] == s[idx2]:
                    idx1 += 1
                    idx2 += 1
                if idx2 < n and s[idx2] > s[idx1]:
                    best = i
        return s[best:]

    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        n = len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = j + (j - i) if i + k > j else j
                j = i + 1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        max_idx = 0
        curr_idx = 1
        while curr_idx <= len(s) - 1:
            step = 0
            while curr_idx + step <= len(s) - 1 and s[curr_idx + step] == s[max_idx + step]:
                step += 1
            
            if curr_idx + step == len(s):
                break
            
            # s[curr_idx + step] != s[max_idx + step]
            if s[curr_idx + step] > s[max_idx + step]:
                max_idx = curr_idx
                curr_idx = curr_idx + 1
            else:
                curr_idx = curr_idx + step + 1
        return s[max_idx:]

class Solution:  
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i = j
                    j += 1
                else:
                    j += offset + 1
                offset = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        # find all indexes of last lex char
        # for all those indices, compare next char, eliminate non-last lex
        # continue until there is only one index
        # append the rest of the string
        
        char_index_map = collections.defaultdict(list)
        for i in range(len(s)):
            char_index_map[s[i]].append(i)
        
        largeC = max(char_index_map)
        starts = {}
        for i in char_index_map[largeC]:
            starts[i] = i+1
        
        while len(starts) > 1:
            to_delete = set()
            next_chars = collections.defaultdict(list)
            
            for start, end in list(starts.items()):
                if end == len(s):
                    to_delete.add(start)
                    continue
                
                next_chars[s[end]].append(start)
                
                if end in starts:
                    to_delete.add(end)
                
            next_starts = {}
            largeC = max(next_chars)
            for start in next_chars[largeC]:
                if start not in to_delete:
                    next_starts[start] = starts[start] + 1
            
            starts = next_starts.copy()
        
        for start in starts:
            return s[start:]
        


class Solution:       
    def lastSubstring(self, s: str) -> str:
        curr_value = 0
        max_value = 0
        max_idx = 0
        char_to_id = {c: i for i, c in enumerate(sorted(set(s)))}
        
        for i in range(len(s) - 1, -1, -1):
            curr_value = char_to_id[s[i]] + curr_value / len(char_to_id)

            if curr_value > max_value:
                max_value = curr_value
                max_idx = i

        return s[max_idx:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        
        
        n = len(s);
        cur = ord(s[0]);
        indices = [0,0];
        
        i=1;
        
        while i<n:
            
            if cur > ord(s[i]):
                indices[1]+=1;
                i+=1;
            elif cur < ord(s[i]):
                indices = [i,i];
                cur = ord(s[i]);
                i+=1;
            else:
                k = indices[0]+1;
                prev= i;
                i+=1;
                while k<prev and i<n:
                    if ord(s[k]) > ord(s[i]):
                        indices[1] =i;
                        break;
                    elif ord(s[i]) > cur:
                        indices = [i,i];
                        cur = ord(s[i]);
                        break;
                    elif ord(s[k]) < ord(s[i]):
                        print(prev,i);
                        indices = [prev,i];
                        break;
                    i+=1;
                    k+=1;
                
                if i==n:
                    indices[1]=n-1;
                if k==prev:
                    indices[1]=i;
        return s[indices[0]:(indices[1]+1)];

class Solution:
    def lastSubstring(self, s: str) -> str:
        
        def find(s, candidates, step):
            if len(candidates) == 1:
                return candidates[0]
            max_char = max(s[i+step] for i in candidates if i+step < len(s))
            new_candidates = [i for i in candidates if i+step < len(s) and s[i+step] == max_char]
            return find(s, new_candidates, step + 1)
        
        if not s: return s
        if len(set(s)) == 1: return s
        
        index = find(s, list(range(len(s))), 0)
        return s[index:]
        
        
            
            
            
        
        
        
        


class Solution:
    def lastSubstring(self, s: str) -> str:
        # loop to find the max lexicographic  
        # substring in the substring array 
        # l = \"\" 
        # for i in range(len(s)-1,-1,-1): 
        #     l = max(l, s[i:]) 
        #     print(s[i:])
        # return l
        if len(set(s)) == 1: return s 
        idx = len(s) - 1
        for i in range(len(s)-2, -1, -1):
            k = 0
            while idx+k < len(s):
                cur, stored = ord(s[i+k]), ord(s[idx+k])
                if cur > stored:
                    idx = i
                    break
                elif cur < stored:
                    break
                k += 1
            if idx+k == len(s):
                idx = i
        return s[idx:]

class Solution:
    def lastSubstring(self, s):
        i, j, inc = 0, 1, 0
        while j + inc < len(s):
          if s[i + inc] == s[j + inc]:
            inc += 1
          elif s[i + inc] > s[j + inc]:
            j += inc + 1
            inc = 0
          else:
            i = j
            j = i + 1
            inc = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,k,n = 0,1,0,len(s)
        while j + k < n:
            if s[i+k] == s[j+k]:
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j = j+k+1
            else:
                i = i+k+1
            if i==j:
                j = j+1
            k = 0
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,offset=0,1,0
        while i+offset < len(s) and j+offset < len(s):
            if s[i+offset]==s[j+offset]:
                offset+=1
            
            else:
                if s[i+offset]<s[j+offset]:
                    i+=offset+1
                else:
                    j+=offset+1
                if i>=j:
                    j=i+1
                offset=0
                    
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,off = 0,1,0
        while i+off<len(s) and j+off<len(s):
            if s[i+off]==s[j+off]:
                off+=1
            else:
                if s[i+off]>s[j+off]:
                    j+=1
                else:
                    i = j
                    j = j+1
                off = 0
        return s[i:]
                
            


class Solution:
    def lastSubstring(self, s: str) -> str:
        if not s: return None
        # get max char from s
        max_char = max(s)
        max_idxs = []
        # get all max_char indexs to append into max_idxs
        for i in range(len(s)):
            if s[i]==max_char:
                ## only store the first ind for consecutive max chars
                if not max_idxs or s[i-1]!=max_char:
                    max_idxs.append(i)
        # also append the length of s into the max_idxs for compersion
        max_idxs.append(len(s))
        #print(max_idxs)
        # initialize the temp max letter
        max_substring = s[max_idxs[0]:max_idxs[1]]
        ans_idx = max_idxs[0]
        
        # using for loop to compare with each short letter those leading by max_char
        for i in range(1, len(max_idxs)-1):
            cur = s[max_idxs[i]:max_idxs[i+1]]
            #print(cur)
            if max_substring==cur[:len(max_substring)]: #  like \"zazaa\" case
                max_substring = max_substring + cur
                ans_idx = max_idxs[i-1] 
            elif max_substring<cur:
                max_substring = cur
                ans_idx = max_idxs[i]
                
        return s[ans_idx:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = 1
        offset = 0
        
        while i + offset < len(s) and j + offset < len(s):
            if s[i+offset] == s[j+offset]:
                offset += 1
                
            else:
                if s[i+offset] < s[j+offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                    
                if i == j:
                    j += 1
                
                offset = 0
                
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        i,j,offset=0,1,0
        while i+offset < len(s) and j+offset < len(s):
            if s[i+offset]==s[j+offset]:
                offset+=1
            
            else:
                if s[i+offset]<s[j+offset]:
                    i+=offset+1
                else:
                    j+=offset+1
                if i==j:
                    j+=1
                offset=0
                    
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = 1
        offset = 0
        
        while i + offset < len(s) and j + offset < len(s):
            if s[i+offset] == s[j+offset]:
                offset += 1
                
            else:
                if s[i+offset] < s[j+offset]:
                    i += offset+1
                else:
                    j += offset+ 1
                
                if i == j:
                    j += 1
                offset = 0
                    
        return s[i:]

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        left = 0; right = 1
        step = 0
        
        while right+step < n:
            if s[right+step] > s[left+step]:
                left, right, step = right, right+1, 0
            elif s[right+step] < s[left+step]:
                right, step = right+step+1, 0
            else:
                step += 1
                    
        return s[left:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        i = 0
        k = 0
        j = 1
        while j+k<len(s):
            if s[i+k] == s[j+k]: 
                k += 1
                continue
            elif s[i+k] > s[j+k]:
                j += 1
            else:
                i += 1
                
            if i == j:
                j += 1
            k = 0
        return s[i:]

from heapq import *

class Solution:
    def lastSubstring(self, s: str) -> str:
        maxc = max(s)
        layer = []
        for i, c in enumerate(s):
            if c == maxc:
                layer.append((c, i, i)) # (char, cur, start)
                
        N = len(s)
        ss = set(i for _,_,i in layer)
        while len(layer) > 1:
            nc = max(s[j+1] for _, j, i in layer if j+1 < N)
            newlayer = []
            todelete = set()
            for _, j, i in layer:
                if j+1 < N and s[j+1] == nc and j+1 in ss:
                    todelete.add(j+1)
            for _, j, i in layer:
                if j+1 < N and s[j+1] == nc and i not in todelete:
                    newlayer.append((nc, j+1, i))
            layer = newlayer
        
        _, cur, start = layer[0]
        return s[start:]
        


# test case - \"acting\" for explanation
class Solution: 
    def lastSubstring(self, s: str) -> str:
        i = 0
        j = 1
        k = 0
        n = len(s)
        while j+k < n:
            if s[i+k] == s[j+k]:
                k+=1
                continue
            elif s[i+k] > s[j+k]:
                j = j + k + 1
            else:
                i = max(i+k+1, j)
                j = i + 1
            k = 0
        return s[i:]


class Solution:
    def lastSubstring(self, s: str) -> str:
        
        i = 0
        j = i + 1
        k = 0
        while  j + k < len(s):
            if s[i + k] == s[j + k]:
                k = k + 1
                continue
            elif s[i + k] > s[j + k]:
                j = j + 1
            else:
                i = max(i+k+1,j)
                j = i +1
            k = 0
        return s[i:]


class Solution:  
    def lastSubstring(self, s: str) -> str:
        i, j, offset = 0, 1, 0
        while i + offset < len(s) and j + offset < len(s):
            if s[i + offset] == s[j + offset]:
                offset += 1
            else:
                if s[i + offset] < s[j + offset]:
                    i += offset + 1
                else:
                    j += offset + 1
                if i == j:
                    j += 1
                offset = 0
        return s[i:]