You can introduce multiple types of changes, for example: addition at the end, removal of N characters from the end, and complete string replacement, etc. Then for each change you can calculate which type is more efficient to store.