def longest_word_sort(words: list[str]) -> str:
    """Returns the longest word character composable from other words in input array

    Complexity:
        n = len(words), m = len(max(words))
        Time: O(nlogn) * O(m) = O((n*m)logn)
            - String comparisons are O(m) in the worst case all strings are
            the same length and must be fully compared
        Space: O(n)
            - O(n): for the timsort auxillary sort space
            - O(n): for the words set space

    Args:
        words: array of strings words representing an English Dictionary

    Returns:
        the longest word in words that can be built one character at a time by
        other words in words. If there is more than one possible answer,
        returns the longest word with the smallest lexicographical order,
        otherwise the empty string.

    Examples:
        >>> longest_word_sort(["w","wo","wor","worl","world"])
        'world'
        >>> longest_word_sort(["a","banana","app","appl","ap","apply","apple"])
        'apple'
        >>> longest_word_sort(["a","b","banana","app","appl","ap","apple","apply"])
        'apple'

    """

    """ALGORITHM"""
    words.sort()

    ## INITIALIZE VARS ##
    # DS's/res
    words_set = {""}  # The empty string is the longest proper prefix to single chars
    longest_word = ""

    for word in words:
        longest_proper_prefix = word[:-1]

        # If the longest proper prefix (all chars up to, but not including,
        # the last char) of `word` has been seen, this implies `word` is
        # buildable from prefix substrings in `words`.
        #
        # Correctness explanation:
        #   since we are iterating in sorted order,
        #   if `word` is buildable from prefix substrings in `words`,
        #   these prefix substrings are *guaranteed* to have been visited before `words`
        #   so the algorithm is, in turn, guaranteed to be correct
        if longest_proper_prefix in words_set:
            words_set.add(word)

            # since sorting lexicographically orders words,
            # this conditional branch implicitly handles the case where
            # multiple words are bigger than the current longest word and
            # have the same length since the lexicographically smaller word
            # will always be added first
            if len(word) > len(longest_word):
                longest_word = word

    return longest_word