Question

1163. 按字典序排在最后的子串

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)$。

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:]

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);
  }
}

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);
  }
};

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:]
}

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);
}