3403. Find the Lexicographically Largest String From the Box I

You are given a string word, and an integer numFriends.

Alice is organizing a game for her numFriends friends. There are multiple rounds in the game, where in each round:

• word is split into numFriends non-empty strings, such that no previous round has had the exact same split.
• All the split words are put into a box.

Find the lexicographically largest string from the box after all the rounds are finished.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.

vector<int> SA(string& s) {
    int n = s.size(), t = 1;
    vector<int> sa(n), tg(n + 1), g(n + 1);
    for(int i = 0; i < n; i++) sa[i] = i, g[i] = s[i]-'a';
    while(t <= n) {
        g[n] = -1;
        auto cmp = [&](int x, int y) {
            if(g[x] == g[y]) return g[x + t] < g[y + t];
            return g[x] < g[y];
        };

        sort(begin(sa), end(sa), cmp);

        tg[sa[0]] = 0;
        for(int i = 1; i < n; i++) tg[sa[i]] = tg[sa[i-1]] + cmp(sa[i-1], sa[i]);

        swap(g,tg);
        t <<= 1;
    }
    return sa;
}

class Solution {
public:
    string answerString(string word, int numFriends) {
        if(numFriends == 1) return word;
        vector<int> sa = SA(word);
        int len = word.size() - numFriends + 1;
        string res = "";
        return word.substr(sa.back(), len);
    }
};