1163. 按字典序排在最后的子串-解题思路推导

1163. 按字典序排在最后的子串-解题思路推导

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

示例 1：

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

示例 2：

输入：s = “leetcode”
输出：“tcode”

关于这一题 ，大家可能会看到很多解题思路，但是呢，其实很多人自己怎么做出来的都不懂，就照搬照抄，我这里就详细说一下这个题目
1.首先大家看一个图片：

对于上面这个字符串，最大的字符是哪个？
anwser is very easy to carry.
最大的字符是C,这非常明显，那么看我们的题目找出它的所有子串并按字典序排列，返回排在最后的那个子串。
其实就是找出最大的子串，我想问最大子串一定是从最大的字符开始的，这个肯定是的吧，所以呢，我们第一步解题思路，找出最大的字符，其实就是C,代码还是很好写的吧，我这里给出代码

  int init_max_index=0;
   
    for(int i=1;s[i]!='\0';i++){
        if(s[i]>s[init_max_index]){
            init_max_index=i;
        }
    }
    
1
2
3
4
5
6
7
8

是不是上面的代码，s[init_max_index]指的就是最大字符，另外我想问，最大值字串一定是从整个字符串从某个下标开始到最优一个字符串吧，这个很好理解的，因为 aa>a aaa>aa abcc>abc ccbb>ccb ,这四个例子可以很好的帮助我们理解了吧。

那么问题又来了，如果最大字符有很多，怎么办，是的，如果有很多那就一个一个比较，那么继续看这张图片

是不是发现是四个重复的字串串拼接在一起的：

看下面这张图片，最大值能否从s2的某个下标处开始取得，显然不能啊，因为s1在说s2前面，s1==s2，怎么也得从s1开始吧

同理下面这个也是：

所以当我们发现重复字串时，就可以停止继续查找了，综上解题代码如下：

char * lastSubstring(char * s){
    int init_max_index=0;
   
    for(int i=1;s[i]!='\0';i++){
        if(s[i]>s[init_max_index]){
            init_max_index=i;
        }
    }
    
    
     for(int i=0;s[i]!='\0';i++){
        
          if (s[i] != s[init_max_index ]) {
            continue;
        }
        
         if(s[i]==s[init_max_index]&&strcmp(s+i,s+init_max_index)==1){
             init_max_index=i;

         }
         if(s[i]==s[init_max_index]&&i!=init_max_index){
             int j;
             for( j=0;s[i+j]!='\0';j++){
                 if( s[i+j]==s[init_max_index+j]){
                     continue;
                 }
                 else{
                     break;
                 }
                

             }
             if(s[i+j]=='\0'){
                 break;
             }
         }
         
       
     }
    return s+init_max_index;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43