Find the Lexicographically Largest String From the Box I

Find the Lexicographically Largest String From the Box I - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "abc", numFriends = 2

› Output: "c"

💡 Note: Possible splits: ["a","bc"], ["ab","c"]. All substrings: "a", "bc", "ab", "c". Lexicographically largest is "c".

Example 2 — Single Friend

$ Input: word = "aba", numFriends = 1

› Output: "aba"

💡 Note: Only one split possible: ["aba"]. The answer is the word itself.

Example 3 — Multiple Friends

$ Input: word = "abac", numFriends = 3

› Output: "c"

💡 Note: Many possible splits into 3 parts. All possible substrings include "a", "b", "c", "ab", "ba", "ac", etc. The largest is "c".

Constraints

1 ≤ word.length ≤ 10³
1 ≤ numFriends ≤ word.length
word consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Word 'abc' with numFriends = 2

Process

All possible splits and their substrings

Output

Lexicographically largest substring 'c'

Key Takeaway

🎯 Key Insight: The answer is always the lexicographically largest substring of the original word

Asked in

G Google 25 M Microsoft 20

The key insight is that the answer is always the lexicographically largest substring of the original word, regardless of how we split it. Best approach is to find all substrings and return the largest one. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Substring Search	O(n³)	O(n)	Find the lexicographically largest substring directly without generating splits
Generate All Splits	O(C(n-1, k-1) * n)	O(C(n-1, k-1) * n)	Generate all possible splits and find the lexicographically largest string

Direct Substring Search — Algorithm Steps

Iterate through all possible substrings
Compare each substring lexicographically
Return the largest one found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Consider all possible substrings of the word

Compare Lexicographically

Track the largest substring seen so far

Return Result

The largest substring is our answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* word, int numFriends) {
    int n = strlen(word);
    char* maxString = (char*)malloc((n + 1) * sizeof(char));
    strcpy(maxString, "");
    
    // Find the lexicographically largest substring
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int len = j - i;
            char* substring = (char*)malloc((len + 1) * sizeof(char));
            strncpy(substring, word + i, len);
            substring[len] = '\0';
            
            if (strcmp(substring, maxString) > 0) {
                strcpy(maxString, substring);
            }
            
            free(substring);
        }
    }
    
    return maxString;
}

int main() {
    char word[1001];
    int numFriends;
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    scanf("%d", &numFriends);
    
    char* result = solution(word, numFriends);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings, each comparison takes O(n) time in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Only store the current maximum substring

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Substring Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler