Skip to content

3403. Find the Lexicographically Largest String From the Box I

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  string answerString(string word, int numFriends) {
    if (numFriends == 1)
      return word;
    const string s = lastSubstring(word);
    const size_t sz = word.length() - numFriends + 1;
    return s.substr(0, min(s.length(), sz));
  }

 private:
  // Same as 1163. Last Substring in Lexicographical Order
  string lastSubstring(string s) {
    int i = 0;
    int j = 1;
    int k = 0;

    while (j + k < s.length())
      if (s[i + k] == s[j + k]) {
        ++k;
      } else if (s[i + k] > s[j + k]) {
        // Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
        // lexicographically larger substring since s[i..i + k) == s[j..j + k)
        // and s[i + k] > s[j + k).
        j = j + k + 1;
        k = 0;
      } else {
        // Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
        // possible lexicographically larger substring since
        // s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
        // Note that it's unnecessary to explore s[i + k + 1..j) if
        // i + k + 1 < j since they are already explored by j.
        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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public String answerString(String word, int numFriends) {
    if (numFriends == 1)
      return word;
    final String s = lastSubstring(word);
    final int sz = word.length() - numFriends + 1;
    return s.substring(0, Math.min(s.length(), sz));
  }

  // Same as 1163. Last Substring in Lexicographical Order
  private String lastSubstring(String s) {
    int i = 0;
    int j = 1;
    int k = 0; // the number of the same letters of s[i..n) and s[j..n)

    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)) {
        // Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
        // lexicographically larger substring since s[i..i + k) == s[j..j + k)
        // and s[i + k] > s[j + k).
        j = j + k + 1;
        k = 0;
      } else {
        // Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
        // possible lexicographically larger substring since
        // s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
        // Note that it's unnecessary to explore s[i + k + 1..j) if
        // i + k + 1 < j since they are already explored by j.
        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
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  def answerString(self, word: str, numFriends: int) -> str:
    if numFriends == 1:
      return word
    s = self._lastSubstring(word)
    sz = len(word) - numFriends + 1
    return s[:min(len(s), sz)]

  # Same as 1163. Last Substring in Lexicographical Order
  def _lastSubstring(self, s: str) -> str:
    i = 0
    j = 1
    k = 0  # the number of the same letters of s[i..n) and s[j..n)

    while j + k < len(s):
      if s[i + k] == s[j + k]:
        k += 1
      elif s[i + k] > s[j + k]:
        # Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
        # lexicographically larger substring since s[i..i + k) == s[j..j + k)
        # and s[i + k] > s[j + k).
        j = j + k + 1
        k = 0
      else:
        # Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
        # possible lexicographically larger substring since
        # s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
        # Note that it's unnecessary to explore s[i + k + 1..j) if
        # i + k + 1 < j since they are already explored by j.
        i = max(i + k + 1, j)
        j = i + 1
        k = 0

    return s[i:]