Problem of The Day: Find the Lexicographically Largest String From the Box I

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        res = ['']
        N = len(word)
        word_list = list(word)
        max_allowed = N - numFriends + 1
        seen = set()

        def dfs(start, curr, remain_word):
            if len(curr) == numFriends:
                if tuple(curr) in seen:
                    return
                seen.add(tuple(curr))
                ans = sorted(curr)[-1]
                if res[0] <= ans:
                    res[0] = ans
                return

            for i in range(max_allowed):
                if remain_word[:start + 1] == "":
                    continue
                dfs(i, curr + [remain_word[:start + 1]], remain_word[start+1:])

        for i in range(max_allowed):
            dfs(i, [], word)

        return res[0]

Improved Algorithm [TLE]

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        res = ['']
        N = len(word)
        max_allowed = N - numFriends + 1

        @cache
        def dfs(start, remain_word, num_friends):
            if num_friends == numFriends:
                return

            for i in range(max_allowed):
                if remain_word[:start + 1] == "":
                    continue
                if res[0] <= remain_word[:start + 1]:
                    res[0] = remain_word[:start + 1]
                dfs(i, remain_word[start+1:], num_friends + 1)

        for i in range(max_allowed):
            dfs(i, word, 0)

        return res[0]

Editorial

Approach 1: Enumeration

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

Approach 2: Two Pointers

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

    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        last = self.lastSubstring(word)
        n, m = len(word), len(last)
        return last[: min(m, n - numFriends + 1)]