1163. Last Substring in Lexicographical Order LeetCode Solution

In this guide, you will get 1163. Last Substring in Lexicographical Order LeetCode Solution with the best time and space complexity. The solution to Last Substring in Lexicographical Order problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Last Substring in Lexicographical Order solution in C++
4. Last Substring in Lexicographical Order solution in Java
5. Last Substring in Lexicographical Order solution in Python
6. Additional Resources

Problem Statement of Last Substring in Lexicographical Order

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: s = “abab”
Output: “bab”
Explanation: The substrings are [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]. The lexicographically maximum substring is “bab”.

Example 2:

Input: s = “leetcode”
Output: “tcode”

Constraints:

1 <= s.length <= 4 * 105
s contains only lowercase English letters.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

1163. Last Substring in Lexicographical Order LeetCode Solution in C++

class Solution {
 public:
  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[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);
  }
};
/* code provided by PROGIEZ */

1163. Last Substring in Lexicographical Order LeetCode Solution in Java

class Solution {
  public 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);
  }
}
// code provided by PROGIEZ

1163. Last Substring in Lexicographical Order LeetCode Solution in Python

class Solution:
  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:]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.