Skip to content

3406. Find the Lexicographically Largest String From the Box II πŸ”’

Description

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.

 

Example 1:

Input: word = "dbca", numFriends = 2

Output: "dbc"

Explanation:

All possible splits are:

  • "d" and "bca".
  • "db" and "ca".
  • "dbc" and "a".

Example 2:

Input: word = "gggg", numFriends = 4

Output: "g"

Explanation:

The only possible split is: "g", "g", "g", and "g".

 

Constraints:

  • 1 <= word.length <= 2 * 105
  • word consists only of lowercase English letters.
  • 1 <= numFriends <= word.length

Solutions

Solution 1

Thinking

As in Box I, the lexicographically largest piece is a prefix of some suffix, of length at most \(n-\textit{numFriends}+1\). Comparing every left endpoint pairwise is the same idea with a worse constant.

Once the lexicographically largest suffix of the whole string is known, its prefix of the allowed length is the answer.

We therefore compute \(\textit{lastSubstring}\) with two pointers: the current best start \(i\) and a challenger \(j\), advancing over the shared prefix and discarding the weaker side on a mismatch. If \(\textit{numFriends}=1\), we still return the original word.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        s = self.lastSubstring(word)
        return s[: len(word) - numFriends + 1]

    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] < s[j + k]:
                i += k + 1
                k = 0
                if i >= j:
                    j = i + 1
            else:
                j += k + 1
                k = 0
        return s[i:]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        String s = lastSubstring(word);
        return s.substring(0, Math.min(s.length(), word.length() - numFriends + 1));
    }

    public String lastSubstring(String s) {
        int n = s.length();
        int i = 0, j = 1, k = 0;
        while (j + k < n) {
            int d = s.charAt(i + k) - s.charAt(j + k);
            if (d == 0) {
                ++k;
            } else if (d < 0) {
                i += k + 1;
                k = 0;
                if (i >= j) {
                    j = i + 1;
                }
            } else {
                j += k + 1;
                k = 0;
            }
        }
        return s.substring(i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        string s = lastSubstring(word);
        return s.substr(0, min(s.length(), word.length() - numFriends + 1));
    }

    string lastSubstring(string& s) {
        int n = s.size();
        int i = 0, j = 1, k = 0;
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {
                ++k;
            } else if (s[i + k] < s[j + k]) {
                i += k + 1;
                k = 0;
                if (i >= j) {
                    j = i + 1;
                }
            } else {
                j += k + 1;
                k = 0;
            }
        }
        return s.substr(i);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func answerString(word string, numFriends int) string {
    if numFriends == 1 {
        return word
    }
    s := lastSubstring(word)
    return s[:min(len(s), len(word)-numFriends+1)]
}

func lastSubstring(s string) string {
    n := len(s)
    i, j, k := 0, 1, 0
    for j+k < n {
        if s[i+k] == s[j+k] {
            k++
        } else if s[i+k] < s[j+k] {
            i += k + 1
            k = 0
            if i >= j {
                j = i + 1
            }
        } else {
            j += k + 1
            k = 0
        }
    }
    return s[i:]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function answerString(word: string, numFriends: number): string {
    if (numFriends === 1) {
        return word;
    }
    const s = lastSubstring(word);
    return s.slice(0, word.length - numFriends + 1);
}

function lastSubstring(s: string): string {
    const n = s.length;
    let i = 0;
    for (let j = 1, k = 0; j + k < n;) {
        if (s[i + k] === s[j + k]) {
            ++k;
        } else if (s[i + k] < s[j + k]) {
            i += k + 1;
            k = 0;
            if (i >= j) {
                j = i + 1;
            }
        } else {
            j += k + 1;
            k = 0;
        }
    }
    return s.slice(i);
}

Comments