3403: Find-the-Lexicographically-Largest-String-From-the-Box-I
Medium

Enumeration:

Easiest way would just to be to find all the possible substrings and compare each one.

Code:

class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) return word;
        int f = 0;
        string ans = word.substr(0, word.size()-numFriends+1);
        for (int i = 0; i < word.size(); ++i) {
            string temp = word.substr(i, word.size()-numFriends+1);
            ans = max(ans, temp);
        }
        return ans;
    }
};

Complexity:

Time Taken:

Two Pointers:

The intuition to this solution is, since we are trying to find the lexigraphically largest substring, it implies that we can stop keeping track of the previous largest substring if it is smaller than the current substring.

Since, we can determine whether or not a substring is greater than another substring simply by comparing the letters present at respective indices, it makes intuitive sense to use some sort of two-pointers solution, to keep track of the letter present in both strings.

In fact, we can simplify this even further;

Code:

class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) return word;

        int n = word.size();
        int l = 0, r = 1, k;

        while (r < n) {
            k = 0;
            // while the letters in both substring are equal, just keep iterating
            while (r + k < n && word[l+k] == word[r+k]) {
                ++k;
            }

            // example:
            // M I A M I A N E E
            // `M` vs `I` - l = 0, r = 1, k = 0
            // `M` vs `A` - l = 0, r = 2, k = 0
            //  --- beginning of "while" loop ---
            // `M` vs `M` - l = 0, r = 3, k = 0
            // `M I` vs `M I` - l = 0, r = 3, k = 1
            // `M I A` vs `M I A` - l = 0, r = 3, k = 2
            // `M I A M` vs `M I A N` - l = 0, r = 3, k = 3
            //  --- ending of "while" loop ---
            //  --- realised `N` > `M`, so `l = r` and `r = max(r+1, l+k+1)` ---
            // `M` vs `I` - l = 3, r = 4, k = 0
            // `M` vs `A` - l = 3, r = 5, k = 0
            // `M` vs `N` - l = 3, r = 6, k = 0
            //  --- realised `N` > `M`, so `l = r` and `r = max(r+1, l+k+1)` ---
            // `N` vs `E` - l = 6, r = 7, k = 0
            // `N` vs `E` - l = 6, r = 8, k = 0

            // therefore, largest suffix starts from index `6`

            // when we reach a different letter:
            // if that different letter is GREATER
            if (r + k < n && word[l+k] < word[r+k]) {
                // set `l = r` as substring starting from `r` is GREATER
                int t = l;
                l = r;
                
                // want to update `r` to the MINIMUM value 
                // we have traversed and verified
                r = max(r+1, t+k+1);
            // if that different letter is SMALLER
            } else {
                r = r + k + 1;
            }
        }

        return word.substr(l, min(n-l, n-numFriends+1));
    }
};

Complexity: