1163.md

Last Substring in Lexicographical Order

题目

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.

understand problem in a simplely way : Imagine adding every possible substring of s to an array and sorting it alphabetically. The problem wants you to return the last string that would be in such array.

e.g. for "bab" the substrings are ["b", "a", "b", "ba", "ab", "bab"], and sorting it results in ["a", "ab", "b", "b", "ba", "bab"]. So the answer is "bab".

思路

总结：
	题目的处理难点在于这种case："zzaaaabbzzd"。
	贪心算法：初始化resIndex = 0，默认结果为s[0:]
	遍历字符串，比较当前字符和下一个字符是否相等，
	如果相等表示该字符开头不可能为候选结果。
	如果不相等表示该字符开头有可能是结果。内存用循环比较是否为结果，如果为结果更新resIndex。不是则继续
		

代码

func lastSubstring(s string) string {
    resIndex := 0
    for i := 0; i < len(s)-1; i++ {
        if s[i] == s[i+1] {
            continue
        }
        for j := 0; i + 1 + j < len(s); j++ {
            if s[resIndex+j] > s[i+1+j] {
                break
            }
            if s[resIndex+j] < s[i+1+j] {
                resIndex = i + 1
                break
            }
        }
    }
    return s[resIndex:]
}