def recursive_replace(steps: int, to_expand: str, rules: dict) -> str:
    """ Replace the given string with a new replacement string, according to the rules.

    Args:
        steps (int): How many iterations. Decremented with each recursion. Recursion ends when step=0.
        input (str): Input str. The str to be replaced at this recursion depth
        rules (dict): Map of XY: Z, such that XY becomes XZY """
    res = to_expand     # E.g. NNCB first iteration, NCN on second iteration, NBC on third...
    chars_inserted = 0  # This grows as we insert horizontally, to allow indexing
    for i in range(len(to_expand)-1):  # sliding window of 2 chars; stop at len-1
        pair = to_expand[i:i+2] # E.g. CB
        if pair in rules:   # if this pair has a valid replacement str
            replacement = pair[0] + rules[pair] + pair[1]   # E.g. CH -> CBH
            insertion_point = i + chars_inserted
            if steps > 1:   # Deeper recursions to go
                # Now recurse into the pair we've just expanded
                replacement = recursive_replace(steps-1, replacement, rules)  
            
            res = res[:insertion_point] + replacement + res[insertion_point+2:]
            
            # Because replacement is recursive, XY could be replaced by a long str
            chars_inserted += len(replacement)-len(pair)
            
    return res