Well, yeah I don't like inefficient code when it can easily be improved in that aspect. OTOH, I prefer easy to read/maintain code.
And I'll have to check again, maybe I was tired, but I found your code oddly hard to follow, and tricky to fix the issues I found. At the time I found that working on path components directly made everything simpler at many level.
And for the matter of otherwise useful reusable functions, yes, but for example I think I remember one bug is that the longest common substring is *not* necessarily what you want here, like in */a/b/c/d/longilename* vs. */z/b/c/y/longfilename*: *longfilename* is obviously the longest substring, but you actually want */b/c/* -- so IIRC your code will just not shorten this because it'll find *longfilename* as the substring, but will rightly ignore it because it the basename. So to fix this the function should be updated to find the longest substring *surrounded by separators*, becoming a lot less useful for other callers.
However yes, if you can fix the issues I'll try and give it a new shot and propose some changes instead of a totally different approach.