Skip to content

Latest commit

 

History

History
201 lines (161 loc) · 5.23 KB

File metadata and controls

201 lines (161 loc) · 5.23 KB
comments difficulty edit_url rating source tags
true
困难
1864
第 150 场周赛 Q4
双指针
字符串

English Version

题目描述

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

 

示例 1:

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

示例 2:

输入:s = "leetcode"
输出:"tcode"

 

提示:

  • 1 <= s.length <= 4 * 105
  • s 仅含有小写英文字符。

解法

方法一:双指针

我们注意到,如果一个子串从位置 $i$ 开始,那么字典序最大的子串一定是 $s[i,..n-1]$,即从位置 $i$ 开始的最长后缀。因此,我们只需要找出字典序最大的后缀子串即可。

我们使用双指针 $i$$j$,其中指针 $i$ 指向当前字典序最大的子串的起始位置,指针 $j$ 指向当前考虑的子串的起始位置。另外,用一个变量 $k$ 记录当前比较到的位置。初始时 $i = 0$, $j=1$, $k=0$

每一次,我们比较 $s[i+k]$$s[j+k]$

如果 $s[i + k] = s[j + k]$,说明 $s[i,..i+k]$$s[j,..j+k]$ 相同,我们将 $k$$1$,继续比较 $s[i+k]$$s[j+k]$

如果 $s[i + k] \lt s[j + k]$,说明 $s[j,..j+k]$ 的字典序更大。此时,我们更新 $i = i + k + 1$,并将 $k$ 重置为 $0$。如果此时 $i \geq j$,那么我们将指针 $j$ 更新为 $i + 1$,即 $j = i + 1$。这里我们跳过了以 $s[i,..,i+k]$ 为起始位置的所有后缀子串,因为它们的字典序一定小于对应的 $s[j,..,j+k]$ 为起始位置的后缀子串。

同理,如果 $s[i + k] \gt s[j + k]$,说明 $s[i,..,i+k]$ 的字典序更大。此时,我们更新 $j = j + k + 1$,并将 $k$ 重置为 $0$。这里我们跳过了以 $s[j,..,j+k]$ 为起始位置的所有后缀子串,因为它们的字典序一定小于对应的 $s[i,..,i+k]$ 为起始位置的后缀子串。

最后,我们返回以 $i$ 为起始位置的后缀子串即可,即 $s[i,..,n-1]$

时间复杂度 $O(n)$,其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$

Python3

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] < s[j + k]:
                i += k + 1
                k = 0
                if i >= j:
                    j = i + 1
            else:
                j += k + 1
                k = 0
        return s[i:]

Java

class Solution {
    public String lastSubstring(String s) {
        int n = s.length();
        int i = 0;
        for (int j = 1, k = 0; j + k < n;) {
            int d = s.charAt(i + k) - s.charAt(j + k);
            if (d == 0) {
                ++k;
            } else if (d < 0) {
                i += k + 1;
                k = 0;
                if (i >= j) {
                    j = i + 1;
                }
            } else {
                j += k + 1;
                k = 0;
            }
        }
        return s.substring(i);
    }
}

C++

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        int i = 0;
        for (int j = 1, k = 0; j + k < n;) {
            if (s[i + k] == s[j + k]) {
                ++k;
            } else if (s[i + k] < s[j + k]) {
                i += k + 1;
                k = 0;
                if (i >= j) {
                    j = i + 1;
                }
            } else {
                j += k + 1;
                k = 0;
            }
        }
        return s.substr(i);
    }
};

Go

func lastSubstring(s string) string {
	i, n := 0, len(s)
	for j, k := 1, 0; j+k < n; {
		if s[i+k] == s[j+k] {
			k++
		} else if s[i+k] < s[j+k] {
			i += k + 1
			k = 0
			if i >= j {
				j = i + 1
			}
		} else {
			j += k + 1
			k = 0
		}
	}
	return s[i:]
}

TypeScript

function lastSubstring(s: string): string {
    const n = s.length;
    let i = 0;
    for (let j = 1, k = 0; j + k < n; ) {
        if (s[i + k] === s[j + k]) {
            ++k;
        } else if (s[i + k] < s[j + k]) {
            i += k + 1;
            k = 0;
            if (i >= j) {
                j = i + 1;
            }
        } else {
            j += k + 1;
            k = 0;
        }
    }
    return s.slice(i);
}