Elegant algorithm for storing words in a string

Question

I have an application in which a user enters text into a user text area. If the user deletes the text area, it moves the cursor to the point they just listened to, which allows them to insert / delete text anywhere in the text area. The restrictions that there cannot be space at the beginning of the text area, and there cannot be consecutive spaces at any point in the text area (there is also no return key to create a new line). The text in the text area is stored in an attribute string called "text".

I need to develop an efficient algorithm that tracks the widest word in the text area. When I speak as broadly as possible, I do not mean the width of the character, but the actual width of the pixel that I calculate by storing the text in CTFrameRef and getting its size.

I came up with a lot of brute force so that this could be done, but I wonder if anyone knows what will be the most effective way for both time and space for this? I obviously need some kind of data structure that tracks every word and its length, and I thought of storing all the words in an array and updating them as the text is inserted or deleted, but I wonder if anyone can think of something- is anything more optimal?

Answer 1

You can do this with min-heap if you can find (or write) one that includes the modify-key operation. You will need both increase-key and decrease-key , but the good news is that both of them are implemented in O (log N).