If the prefix (ie everything except the last character) is uniq, you could strip off the last character, and use the remaning string as a hash key.

In the hash you store a list of matching strings.

When you have created the hash, you should iterate through it and check if the +1/-1 condition holds.