# your code goes here
def longestKinterspaceSubstring(word, k):
    if not word:
        return ""

    n = len(word)
    # dp[i] stores the length of the longest valid substring ending at index i
    dp = [1] * n

    max_len = 1
    max_start = 0

    for i in range(1, n):
        if abs(ord(word[i]) - ord(word[i - 1])) <= k:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = 1

        if dp[i] > max_len:
            max_len = dp[i]
            max_start = i - max_len + 1

    return word[max_start : max_start + max_len]