When you first read the problem “Find the Lexicographically Largest String From the Box”, it might sound complicated 🤔. However, with the right insight, the solution becomes both elegant and efficient. ✨

In this article, we’ll walk through the problem, break down the core concept, and implement the optimal solution in C++, JavaScript, and Python. 💻

📝 Problem Recap

You are given:

• A string word 🧵
• An integer numFriends 👥

The game rules:

• Split word into exactly numFriends non-empty substrings.
• Every possible way to split word counts as a “round.” 🎲
• For each round, put all split substrings into a box 📦.
• After considering all possible rounds, find the lexicographically largest substring in the box. 🔠

💡 Key Insight

At first glance, it looks like we need to consider all ways to split the string, which could be exponential in complexity ⚡.

But here’s the trick:

• If you split a string of length n into numFriends parts, the longest substring in any split must have length at least n - numFriends + 1. 📏

Why?

• Because at minimum, the other numFriends - 1 substrings each have length 1. 🧩
• So the longest substring length is constrained and can be calculated. ✔️

Therefore, the lexicographically largest substring that appears in any valid split must be a substring of word of length exactly n - numFriends + 1. 🔍

🔧 How to Solve It?

• Find the lexicographically largest substring of length n - numFriends + 1.
• Return that substring. 🎯

This approach avoids any heavy recursion or DP 🛠️.

💻 Implementations

C++

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

JavaScript

function answerString(word, numFriends) {
    if (numFriends === 1) return word;
    let length = word.length - numFriends + 1;
    let res = "";
    for (let i = 0; i <= word.length - length; i++) {
        let temp = word.substring(i, i + length);
        if (temp > res) {
            res = temp;
        }
    }
    return res;
}

Python

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        length = len(word) - numFriends + 1
        res = ""
        for i in range(len(word) - length + 1):
            temp = word[i:i+length]
            if temp > res:
                res = temp
        return res

🎯 Conclusion

This problem beautifully demonstrates how understanding problem constraints and properties can simplify seemingly complex problems. 🌟

Instead of brute forcing every split, we reduce the problem to a straightforward substring search, making our solution both simple and efficient. 🧠💡

Feel free to try these implementations, and let me know if you have any questions or want to explore advanced optimizations! 🙌

Happy coding! 👩‍💻👨‍💻🚀