1163. 按字典序排在最后的子串 - Java 双指针

原题地址：https://leetcode.cn/problems/last-substring-in-lexicographical-order/

题解

参考其他题解

假设子串[i,j]为当前最大子串，若j不为s.length()-1，则必然有[i,j+1]>[i,j]，所以字符串的字典序最大子串必然为s的一个后缀，即s.substring(i,s.length())

双指针，设前指针max为当前最大子串起始点，后指针itr为当前遍历子串起始点，k为当前子串被比较字符的偏移值

最初考虑到暴力做法，即每次max++和itr++，然后重新逐个字符比较子串，但是这样有个问题在于会不断比较重复的部分

如abcdabcdb，在比较完abcda和abcdb后，还会比较一次bcda和bcdb，然后还会比较一次cda和cdb…
这样会导致O(N^2)的时间复杂度，在较小数据量时还好说，但是对于[a,a,…,a]这种刁钻样例时是必然TLE的

关键在于如何将两层循环缩减为一层循环，让k每次比较不会比较重复的部分，题解给出的思路非常巧妙

如果对于两个子串满足[max,max+k]=[itr,itr+k]的话，则可以直接循环k++直至max+k和itr+k字符不等
如果对于两个子串满足[max,max+k]>[itr,itr+k]的话
- 我们得出的结论不只是子串[max,end]>[itr,end]，因为这个k的存在，对于任何i<k我们都有子串[max+i,end]>[itr+i,end]，因为[max+i,max+k-1]与[itr+i,itr+k-1]这两部分完全相等，而[max+k]>[itr+k]，此时最大子串必然不在[itr,end]——[itr+k,end]中，所以可以直接推进itr=itr+k+1
如果对于两个子串满足[max,max+k]<[itr,itr+k]的话
- 我们得出的结论不只是子串[max,end]<[itr,end]，因为这个k的存在，对于任何i<k我们都有子串[max+i,end]<[itr+i,end]，因为[max+i,max+k-1]与[itr+i,itr+k-1]这两部分完全相等，而[max+k]<[itr+k]，此时最大子串必然不在[max,end]——[max+k,end]中，所以可以直接推进max=max+k+1
- 此时若max>=itr，则说明itr也在[max,end]——[max+k,end]中，此时itr不存在最大解，可以直接重置itr=max+1

在这种情况下，对于[a,a,…,a]，k会由于max+k==itr+k而不断自增至末尾，在一次比较完后itr+k会直接因为大于s.length()而跳出循环，本质上是因为当我们比较出前指针和后指针两个子串的结果后，对于这两个子串相同的那部分前缀也是共享这个结果的，所以保证了每次子串比较都不会有重复比较的部分，在线性扫描的时间内即可完成循环

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public String lastSubstring(String s) {
        int itr=1,max=0;
        int k=0;
        while (itr+k<s.length()){
            if(s.charAt(itr+k)==s.charAt(max+k)){
                k++;
            }else if(s.charAt(itr+k)<s.charAt(max+k)){
                itr=itr+k+1;
                k=0;
            }else{
                max=max+k+1;
                if(max>=itr)itr=max+1;
                k=0;
            }
        }
        return s.substring(max,s.length());
    }
}