Given a sequence of positive integers in a string, and a positive integer k between 2 and n where n is the number of positive integers in the given string. Return the string that is a size k sequence of the given string that represents the largest number.

max_seq.py

"""
Given a sequence of positive integers in a string, and a positive integer k between 2 and n where n is the number of positive integers in the given string,
Return the string that is a size k sequence of the given string that represents the largest number. 

Example:

Input: '85888900', 3
Output: '900'

"""

import heapq

def max_seq(word, k):

    n = len(word)
    if k == n:
        return word

    # Create list of pairs. Integer pairs with its index to keep the order. 
    check = [-1 * int(x) for x in word]
    pairs = list(zip(check, range(n)))
    # Create max heap of the first n - k integers. Time Complexity: O(n - k + 1)
    max_heap = pairs[:-(k - 1)]
    heapq.heapify(max_heap)

    index = -1
    ret = list()

    # Iterate from index n-k to k. Continue popping the largest value until index value (second value of the pair)
    # is greater than cur_index. Add the most recently popped value to the ret list.  Then push the next 
    # integer in the string into the max heap.
    # Time Complexity: O(nlog(n - k + 1))
    for i in range(n - k, n):
        cur_index = index
        while cur_index >= index:
            cur = heapq.heappop(max_heap)
            index = cur[1]
        ret.append(str(-1 * cur[0]))
        if i < n - 1:
            heapq.heappush(max_heap, pairs[i + 1])

    return "".join(ret)

Cases:

[6, 5, 5, 9, 0] , 3 - > [6, 9 0]

[0, 0, 0, 0, 0], 2 - > [0, 0]

[1, 1, 1, 0, 0, 0], 3 - > [1, 1, 1]