Find the Lexicographically Largest String From the Box I - Solution & Explanation

Problem Overview: You are given a string s and an integer k. The string is split into k non‑empty substrings. Among all substrings placed in the box, return the lexicographically largest possible string that could appear.

Approach 1: Enumerate Substring Left Endpoints (O(n²) time, O(1) extra space)

The key constraint is that all k substrings must be non‑empty. If a substring starts at index i, the remaining characters must still be enough to form the other k-1 substrings. That limits the maximum length of the current substring to n - i - (k - 1). Iterate through every possible starting index and construct the longest valid substring beginning there. Compare each candidate using standard lexicographical comparison and keep the maximum.

This works because a longer prefix with a larger leading character dominates lexicographically. By always taking the maximum allowed length for each start index, you ensure the candidate is the best possible substring beginning at that position. The algorithm is straightforward: iterate through the string, compute the valid substring length, extract the candidate, and update the best answer if it is larger.

Although substring comparison can cost up to O(n), the total complexity remains O(n²) in the worst case, which is acceptable for typical constraints in medium string problems. The implementation relies entirely on basic string operations and simple iteration.

This problem mainly tests understanding of string comparison rules and careful boundary calculation while enumerating candidates. Some implementations also optimize comparisons using two pointers to avoid unnecessary substring creation, but the core idea remains enumerating valid starting points.

Recommended for interviews: Enumerating substring start positions is the expected approach. A brute-force mindset shows you understand the search space, but correctly limiting substring length using the k constraint demonstrates stronger reasoning about problem constraints and lexicographical ordering.