[Swift]LeetCode1163. 按字典序排在最后的子串 | Last Substring in Lexicographical Order

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（www.zengqiang.org）

➤GitHub地址：https://github.com/strengthen/LeetCode

➤原文地址：

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Example 1:

Input: 

Example 2:

Input: 

Note:

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

---

给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：

输入："abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2：

输入："leetcode"
输出："tcode"

提示：

1. 1 <= s.length <= 10^5
2. s 仅含有小写英文字符。

---

Runtime: 168 ms

Memory Usage: 22.9 MB

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         let arrS:[Character] = Array(s)
 4         var i:Int = 0
 5         let len:Int = s.count
 6         for j in 1..<len
 7         {
 8             var sz:Int = 0
 9             while(j + sz < len)
10             {
11                 if arrS[i + sz] == arrS[j + sz]
12                 {
13                     sz += 1
14                     continue
15                 }
16                 i = arrS[j + sz] > arrS[i + sz] ? j : i
17                 break                
18             }
19             if j + sz == len
20             {
21                 break
22             }
23         }        
24         return s.subString(i)
25     }
26 }
27 
28 extension String {
29     // 截取字符串：从index到结束处
30     // - Parameter index: 开始索引
31     // - Returns: 子字符串
32     func subString(_ index: Int) -> String {
33         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
34         return String(self[theIndex..<endIndex])
35     }    
36 }

---

224ms

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3                 
 4         let chars = Array(s)
 5         var highest: Character = "A"
 6         var idxs = [Int]()
 7         var distinct = 0
 8         for i in chars.indices {
 9             if chars[i] > highest {
10                 highest = chars[i]
11                 idxs = [Int]()
12                 distinct += 1
13             }
14 
15             if chars[i] == highest {
16                 idxs.append(i)
17             } else {
18                 distinct += 1
19             }
20         }
21 
22         if distinct == 1 {
23             return s
24         }
25 
26         var shift = 1;
27 
28         var nextLevel = [Int]()
29 
30         while idxs.count > 1 {
31             var shiftHighest: Character = "A"
32             for i in idxs {
33                 if i + shift < chars.count {
34                     if chars[i+shift] > shiftHighest {
35                         shiftHighest = chars[i+shift]
36                         nextLevel = [Int]()
37                     }
38                     if chars[i+shift] == shiftHighest {
39                         nextLevel.append(i)
40                     }
41                 }
42             }
43             idxs = nextLevel
44             nextLevel.removeAll()
45             shift += 1
46         }
47         return String(chars[idxs[0]..<chars.count])
48     }
49 }

---

476ms

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         
 4         var ret = s[s.startIndex...]
 5         
 6         for i in s.indices.dropFirst() {
 7             ret = max(ret, s[i...])
 8         }
 9         
10         return String(ret)
11     }
12 }

---

1772ms

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         var maxCharacter = Character(Unicode.Scalar(0))
 4         var maxIndex = 0
 5         
 6         for (index, character) in s.enumerated() {
 7             if character > maxCharacter {
 8                 maxCharacter = character
 9                 maxIndex = index
10             }
11             else if character == maxCharacter, 
12             String(s[String.Index(encodedOffset: index)...]) > String(s[String.Index(encodedOffset: maxIndex)...]) {
13                 maxCharacter = character
14                 maxIndex = index
15             }
16         }
17         
18         return String(s[String.Index(encodedOffset: maxIndex)...])
19     }
20 }