def damerau_levenshtein_distance(s, t, alphabet_size=256):
    m = len(s)
    n = len(t)
    # Initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # Track last occurrence of each character (simulated with a dictionary)
    last_occurrence = dict()
    
    for i in range(1, m + 1):
        # Current character in s
        char_s = s[i-1]
        last_match = 0  # Last position where t[j] == s[i]
        
        for j in range(1, n + 1):
            char_t = t[j-1]
            i_prev = last_occurrence.get(char_t, 0)
            j_prev = last_match
            
            # Compute substitution cost
            cost = 0 if char_s == char_t else 1
            if cost == 0:
                last_match = j
            
            # Update DP for deletion, insertion, substitution
            dp[i][j] = min(
                dp[i-1][j] + 1,      # Deletion
                dp[i][j-1] + 1,      # Insertion
                dp[i-1][j-1] + cost   # Substitution
            )
            
            # Check for transposition using last_occurrence
            if i_prev > 0 and j_prev > 0:
                trans_cost = dp[i_prev-1][j_prev-1] + (i - i_prev - 1) + (j - j_prev - 1) + 1
                dp[i][j] = min(dp[i][j], trans_cost)
        
        # Update last occurrence of current character in s
        last_occurrence[char_s] = i
    
    return dp[m][n]


print(damerau_levenshtein_distance('corectins','correcting'))
'''{'ther,': ['there'], 'thead': ['the', 'thee', 'their', 'there'], 'hter': ['the', 'thee', 'their', 'there']}
   {'thead': ['the', 'thee', 'their', 'there'], 'ther': ['the', 'thee', 'their', 'there'], 'hter': ['the', 'thee', 'their', 'there']}'''

tests = [
    ("hello", ["helo", "Heello", "helpo", "hlelO"]),
    ("hello", ["help", "elhlo", "MELLOW", "shelol"]),
]
for s, xs in tests:
    for x in xs:
        print(s, x.lower(), damerau_levenshtein_distance(s, x.lower()))