Bad boundaries description or tests
It seems there are no tests like this, and it's highly sensitive to task complexity.
fuzzy_string_match("apple", "appxxxle", 3) == True # remove 'xxx' fuzzy_string_match("apple", "ape", 2) == True # insert 'pl' inside fuzzy_string_match("fuzzy", "fuzy", 1) == True # not 2 like in your tests (insert single 'z' inside)