How do you solve Last Substring in Lexicographical Order on LeetCode?

Last Substring in Lexicographical Order (LeetCode #1163) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The answer is always a suffix of the string, which allows us to optimize our search.

What is the brute force solution for Last Substring in Lexicographical Order?

The brute force approach for Last Substring in Lexicographical Order is Brute Force, with O(n²) time complexity and O(n²) space complexity. The brute force approach involves generating all possible substrings of the input string and then comparing them to find the lexicographically largest one. This method is straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Last Substring in Lexicographical Order?

Last Substring in Lexicographical Order uses the following concepts: Two Pointers, String. The recommended patterns to study are: Two Pointers, Suffix Array.

What are the interview tips for Last Substring in Lexicographical Order?

Always think about the constraints — can you optimize for larger inputs? Consider edge cases, like strings with all identical characters or strings of length 1. Practice explaining your thought process clearly and step-by-step.

What are common mistakes when solving Last Substring in Lexicographical Order?

Generating all substrings without realizing the optimal approach exists. Not considering that the answer is a suffix, leading to unnecessary complexity.

#1163

Last Substring in Lexicographical Order

Hard

Two PointersStringTwo PointersSuffix Array

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n²)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses a single pass to identify the lexicographically largest suffix by comparing characters from the end of the string. This is efficient and avoids the overhead of generating all substrings.

⚙️

Algorithm

4 steps

1Step 1: Initialize a variable to track the starting index of the largest substring.
2Step 2: Iterate through the string from the second last character to the first character.
3Step 3: Compare the current character with the character at the current largest index; if it's greater, update the largest index.
4Step 4: After the loop, return the substring starting from the largest index.

solution.py9 lines

1# Full working Python code
2
3def last_substring_optimal(s):
4    largest_index = len(s) - 1
5    for i in range(len(s) - 2, -1, -1):
6        if s[i] > s[largest_index]:
7            largest_index = i
8    return s[largest_index:]
9

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the string. The space complexity is O(1) since we only use a few variables to track indices.

1The answer is always a suffix of the string, which allows us to optimize our search.
2Lexicographical order can be determined by character comparison, similar to dictionary ordering.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.