# 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]

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBsb25nZXN0S2ludGVyc3BhY2VTdWJzdHJpbmcod29yZCwgayk6CiAgICBpZiBub3Qgd29yZDoKICAgICAgICByZXR1cm4gIiIKCiAgICBuID0gbGVuKHdvcmQpCiAgICAjIGRwW2ldIHN0b3JlcyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHZhbGlkIHN1YnN0cmluZyBlbmRpbmcgYXQgaW5kZXggaQogICAgZHAgPSBbMV0gKiBuCgogICAgbWF4X2xlbiA9IDEKICAgIG1heF9zdGFydCA9IDAKCiAgICBmb3IgaSBpbiByYW5nZSgxLCBuKToKICAgICAgICBpZiBhYnMob3JkKHdvcmRbaV0pIC0gb3JkKHdvcmRbaSAtIDFdKSkgPD0gazoKICAgICAgICAgICAgZHBbaV0gPSBkcFtpIC0gMV0gKyAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgZHBbaV0gPSAxCgogICAgICAgIGlmIGRwW2ldID4gbWF4X2xlbjoKICAgICAgICAgICAgbWF4X2xlbiA9IGRwW2ldCiAgICAgICAgICAgIG1heF9zdGFydCA9IGkgLSBtYXhfbGVuICsgMQoKICAgIHJldHVybiB3b3JkW21heF9zdGFydCA6IG1heF9zdGFydCArIG1heF9sZW5d