Skip to content

1163. Last Substring in Lexicographical Order

  • Time: $O(n)$
  • Space: $O(1)$
 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
class Solution {
 public:
  string lastSubstring(string s) {
    int i = 0;
    int j = 1;
    int k = 0;  // Number of same characters of s[i:] and s[j:]

    while (j + k < s.length()) {
      if (s[i + k] == s[j + k]) {
        ++k;
      } else if (s[i + k] > s[j + k]) {
        // Now s[i:i + k] == s[j:j + k] and s[i + k] > s[j + k] means that
        // We should start from s[j + k] to find a possible larger substring
        j += k + 1;
        k = 0;
      } else {
        // Now s[i:i + k] == s[j:j + k] and s[i + k] < s[j + k] means that
        // Either starting from s[i + k + 1] or s[j] has a larger substring
        i = max(i + k + 1, j);
        j = i + 1;
        k = 0;
      }
    }

    return s.substr(i);
  }
};

 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
class Solution {
  public String lastSubstring(String s) {
    int i = 0;
    int j = 1;
    int k = 0; // Number of same characters of s[i:] and s[j:]

    while (j + k < s.length()) {
      if (s.charAt(i + k) == s.charAt(j + k)) {
        ++k;
      } else if (s.charAt(i + k) > s.charAt(j + k)) {
        // Now s[i:i + k] == s[j:j + k] and s[i + k] > s[j + k] means that
        // We should start from s.charAt(j + k) to find a possible larger substring
        j += k + 1;
        k = 0;
      } else {
        // Now s[i:i + k] == s[j:j + k] and s[i + k] < s[j + k] means that
        // Either starting from s[i + k + 1] or s[j] has a larger substring
        i = Math.max(i + k + 1, j);
        j = i + 1;
        k = 0;
      }
    }

    return s.substring(i);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def lastSubstring(self, s: str) -> str:
    i = 0
    j = 1
    k = 0  # Number of same characters of s[i:] and s[j:]

    while j + k < len(s):
      if s[i + k] == s[j + k]:
        k += 1
      elif s[i + k] > s[j + k]:
        # Now s[i:i + k] == s[j:j + k] and s[i + k] > s[j + k] means that
        # We should start from s[j + k] to find a possible larger substring
        j += k + 1
        k = 0
      else:
        # Now s[i:i + k] == s[j:j + k] and s[i + k] < s[j + k] means that
        # Either starting from s[i + k + 1] or s[j] has a larger substring
        i = max(i + k + 1, j)
        j = i + 1
        k = 0

    return s[i:]