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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Amortized analysis

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

Solutions:
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:
		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)
			if curr_value > max_value:
				max_value = curr_value
				max_idx = i
		return s[max_idx:]


class Solution:

	def lastSubstring(self, s: str) -> str:
		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
		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:]


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 = 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):
		(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:
		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:
					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, 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:

		class TreeNode:

			def __init__(self):
				self.children = collections.defaultdict()
		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]
		res = ''
		node = root
		while node and len(node.children) > 0:
			for i in range(25, -1, -1):
				c = chr(ord('a') + i)
				if c in node.children:
					node = node.children[c]
					res += c
					break
		return res

	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:
		lenS = len(s)
		largestChar = max(set(s))
		candidateIndexes = []
		repeating = False
		for i in range(lenS):
			if s[i] == largestChar:
				if repeating == False:
					candidateIndexes.append(i)
					repeating = True
			else:
				repeating = False
		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:
		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:
					continue
				if start + offset == n:
					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:
		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
		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:
		if not s:
			return None
		(maxC, N) = (max(s), len(s))
		inds = [i for i in range(N) if s[i] == maxC and (i == 0 or s[i - 1] != maxC)]
		maxind = inds[0]
		for i in range(1, len(inds)):
			curind = inds[i]
			step = 0
			while curind + step < N:
				if s[curind + step] > s[maxind + step]:
					maxind = curind
					break
				elif s[curind + step] == s[maxind + step]:
					step += 1
				else:
					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:
		n = len(s)
		offset = 0
		cand_starts = list(range(len(s)))
		while len(cand_starts) > 1:
			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):
				if 1 < idx and cand_starts[idx - 1] + offset == start:
					continue
				if start + offset == n:
					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 = []
		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)
			maxInds = []
			for i in range(len(currArr)):
				if maxNum == currArr[i]:
					maxInds.append(i)
			if len(maxInds) == 1:
				return str(s[maxInds[0]:])
			blockSize += 1
			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
		return sorted(ans)[-1]


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:
		(left, right, length) = (0, 1, 0)
		n = len(s)
		while right + length < n:
			if s[left + length] == s[right + length]:
				length += 1
			elif s[left + length] > s[right + length]:
				right += length + 1
				length = 0
			else:
				left += length + 1
				right = left + 1
				length = 0
		return s[left:]


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:
		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


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]
		maxchar = max(index.keys())
		front = analize(index[maxchar])
		curbest = ''
		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)]
			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:
		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:
		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:
		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
			cands = new_cands
		return s[cands[0][1]:]


class Solution:

	def lastSubstring(self, s: str) -> str:
		if not s:
			return None
		(maxC, N) = (max(s), len(s))
		inds = [i for i in range(N) if s[i] == maxC and (i == 0 or s[i - 1] != maxC)]
		maxind = inds[0]
		for i in range(1, len(inds)):
			curind = inds[i]
			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


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


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:
		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:
		c = max(s)
		r = None
		i = 0
		while i < len(s):
			if s[i] == c:
				if r == None:
					r = i
				elif 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:
		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:
		max_char = 'a'
		chars = []
		for (i, char) in enumerate(s):
			if char >= max_char:
				max_char = char
				chars.append(i)
		max_string = ''
		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:]


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:
		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:
		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


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]:
			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:
		ans = s[0]
		for i in range(len(s)):
			if s[i] < ans[0]:
				continue
			else:
				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


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:
		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:])
		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)
		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


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


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:
		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
			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]:
				length += 1
			elif s[slow + length] > s[fast + length]:
				fast += length + 1
				length = 0
			else:
				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 = ''
		for e in i:
			r = max(r, s[e:])
		return r


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


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:
					if ord(l) > ord(s[p1 + i - p2]):
						p1 = p2
					elif ord(l) == ord(s[p1 + i - p2]):
						pass
					else:
						p2 = -1
				elif 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:
		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
			elif s[second + runner] > s[first]:
				(first, second, runner) = (second + runner, second + runner + 1, 0)
			else:
				(first, second, runner) = (second, second + 1, 0)
		return s[first:]


class Solution:

	def lastSubstring(self, s: str) -> str:
		l = len(s)
		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:
		prev = s[0]
		max_store = []
		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:
		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:]
			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:
				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(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:
		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:
		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 in range(start + 1, len(s)):
				l = s[i]
				if p2 > 0:
					if ord(l) > ord(s[p1 + i - p2]):
						p1 = p2
					elif ord(l) == ord(s[p1 + i - p2]):
						pass
					else:
						p2 = -1
				elif ord(l) > ord(s[p1]):
					p1 = i
				elif ord(l) < ord(s[p1]):
					pass
				else:
					p2 = i
			return p1
		(i, j) = (0, helper(s, 0))
		while j > i:
			(i, j) = (j, helper(s, j))
		return s[j:]


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())
		ids = d[z]
		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]
			elif 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:
		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


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:
			if s[i] == char_max:
				if s[i:] > ans:
					ans = s[i:]
			i -= 1
		return ans


import numpy as np

class Solution:

	def lastSubstring(self, s: str) -> str:
		mx = max(s)
		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:
		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:
		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:
		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:
		return max((s[i:] for i in range(len(s))))


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:
		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:
		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:
		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 = 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
				if j + step == len(s):
					return s[i:]
				if s[i + step] > s[j + step]:
					j += 1
					continue
				else:
					i = j
					j += 1
		return s[i:]


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]
		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:
		n = len(s)
		(pool, c, repeat) = ([], max(set(s)), False)
		for (i, x) in enumerate(s):
			if x == c:
				if not repeat:
					pool.append(i)
					repeat = True
			else:
				repeat = False
		k = 1
		while len(pool) > 1:
			(new_pool, c) = ([], '')
			for i in pool:
				sc = s[i + k] if i + k < n else ''
				if sc > c:
					new_pool = [i]
					c = sc
				elif sc == c:
					new_pool.append(i)
			pool = new_pool
			k += 1
		return s[pool[0]:]


class Solution:

	def lastSubstring(self, s: str) -> str:
		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:
		if not s:
			return None
		max_char = max(s)
		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)
		max_idxs.append(len(s))
		max_letter = s[max_idxs[0]:max_idxs[1]]
		ans_idx = max_idxs[0]
		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:
		begin = 0
		end = 1
		offset = 0
		while end + offset < len(s):
			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:
		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
			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:
		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:

		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:
		if not s:
			return None
		max_char = max(s)
		max_idxs = []
		for i in range(len(s)):
			if s[i] == max_char:
				if not max_idxs or s[i - 1] != max_char:
					max_idxs.append(i)
		max_idxs.append(len(s))
		max_substring = s[max_idxs[0]:max_idxs[1]]
		ans_idx = max_idxs[0]
		for i in range(1, len(max_idxs) - 1):
			cur = s[max_idxs[i]:max_idxs[i + 1]]
			if max_substring == cur[:len(max_substring)]:
				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:]


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))
		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:]