I note that Ying's thesis on repairing bracket structure in XML is a cubic time algorithm. It's not immediately obvious to me that an algorithm computing "optimal" repairs for bracket structures can be faster than quadratic time. Everything hinges on what the requirements actually are. space?
I'm certain that my use of Data.Sequence, and therefore finger trees, has this code at O(1) time. Doesn't using a lazy list mean I am using O(1) space?
If the input has m characters and the output has n characters, the algorithm MUST take at least O(m+n) time. Two people have independently proposed basically the same streaming algorithm taking O(m+n) time and O(1) space with lazy Strings, and one of them proposed an algorithm that would reproduce the few test cases you provided, still with O(m+n) time and O(1) space, without finger or any other trees. Negotiating the specification comes first.