Sign up ×

Suppose I have a list of strings where each string is

  • exactly 4 characters long and
  • unique within the list.

For each of these strings I want to identify the position of the characters within the string that make the string unique.

So for a list of three strings


For the first string I want to identify the character in 4th position d since d does not appear in the 4th position in any other string.

For the second string I want to identify the character in 4th position c.

For the third string it I want to identify the character in 1st position b AND the character in 4th position, also b.

This could be concisely represented as

abcd -> ...d
abcc -> ...c
bbcb -> b..b

If you consider the same problem but with a list of binary numbers


Then the result I want would be

0101 -> ..0.
0011 -> .0..
1111 -> 1...

Staying with the binary theme I can use XOR to identify which bits are unique within two binary numbers since

0101 ^ 0011 = 0110

which I can interpret as meaning that in this case the 2nd and 3rd bits (reading left to right) are unique between these two binary numbers. This technique might be a red herring unless somehow it can be extended to the larger list.

A brute-force approach would be to look at each string in turn, and for each string to iterate through vertical slices of the remainder of the strings in the list.

So for the list


I would start with


and iterate through vertical slices of


where these vertical slices would be

a | b | c | c
b | b | c | b

or in list form, "ab", "bb", "cc", "cb".

This would result in four comparisons

a : ab -> . (a is not unique)
b : bb -> . (b is not unique)
c : cc -> . (c is not unique)
d : cb -> d (d is unique)

or concisely

abcd -> ...d

Maybe it's wishful thinking, but I have a feeling that there should be an elegant and general solution that would apply to an arbitrarily large list of strings (or binary numbers). But if there is I haven't yet been able to see it.

I hope to use this algorithm to to derive minimal signatures from a collection of unique images (bitmaps) in order to efficiently identify those images at a future time. If future efficiency wasn't a concern I would use a simple hash of each image.

Can you improve on brute force?

Edit The approach I'm warming to is building a map of pixels to images

sprawl[Tuple<x=10, y=33,color=f1fefd>] => {

sprawl[Tuple<x=10, y=34,color=f1fef0>] => {

and then using that map to identify the minimal set of signature pixels for each image.

If a pixel (identified by x, y, color) references just one image then I have found a perfect (minimal) signature for that image.

It's more complicated if an image has no unique pixels, but since I know all images are unique within the list I should be able to combine two or more pixel references (but as few as possible) to deduce the image.


I've been working on an algorithm for this. My problem is very similar to this one, and I've written up my algorithm as an answer to that question. This update is to flag the attention of anyone still following (I see five bookmarks). I'm working on this in isolation so any and all feedback is welcome, even if just to observe that I haven't made myself clear!

share|improve this question
If you add bbcd to the list, then some of your items will have no unique characters. How will this affect your goal? – Kathy Van Stone May 18 '10 at 18:05
@Kathy In that case I wouldn't be able to derive the signatures I'm after. For the application in which I hope to use this algorithm that scenario is possible but unlikely. – Ed Guiness May 18 '10 at 18:08
@Ed Guiness, can you describe the "more efficiently identify images at future time" part? Will you be getting some image and you have to tell if it is among the ones you have a signature for? Or will you be asked to find a specific image (which you have a signature for) within a given unknown set of images? If the former, then you are going about it wrongly. If the latter, then your idea of a signature is good (feasible or not). – Aryabhatta May 18 '10 at 18:31
@Moron In the future I will be given a set of identically sized images, all of which I will have seen previously, and I will want to identify each of the images by the most efficient means possible. The best possible result for an image is that it has one pixel that no other image duplicates. In that case I could identify the image by looking at exactly one pixel rather than all pixels (to get a hash). – Ed Guiness May 18 '10 at 18:42
@Ed. So it is the former. Say you had a perfect pixel position for each of the images. How many compares on an average do you think your approach will take? A decision tree might be better suited for this. Check this out:… – Aryabhatta May 18 '10 at 19:06

3 Answers 3

up vote 9 down vote accepted

You can generate a two dimensional array which will contain the number of times each character appears in each position (0-3). For example, arr[1,3] will contain the number of times the digit/character 1 appears in the last position.

Then for each string s, go over all characters in the string. The ones which appear only once in that position according to the array are the unique characters for that string. In other words, if arr[s[i], i]==1 Then string s is unique in position i.

This will give you the solution in linear time, while the algorithm you gave will take quadratic time.

share|improve this answer
From quadratic to linear is always best but I do wonder about the possibility of getting one more item that will simply invalidate all "unique" signatures. The set of strings we can deduce a signature for here is quite contrived (104 = 26*4) so I wonder if the algorithm should not provide for the necessity to use 2 positions / 3 positions etc... What's great about your solution is that it works still: arr[(a,1)(b,3)] could represent the number of times we've seen something matching .a.b... It would not really be linear though, as the number of combination varies in the space of strings. – Matthieu M. May 19 '10 at 6:23

This problem can be solved by trie, or prefix tree.

See Trie - Wikipedia, the free encyclopedia

For the 3 strings in your example:


will be turned into a trie tree (where ^ denotes the root of the tree):

 \      \
  \      c

The path to the node where it branch off are the common prefix. The node after the last branch point is what makes a particular string unique. In this case, they are d, c, b.

I assume the order of string is not important for you, that you compares all strings to find the uniqueness, not just the neighboring string.

The complexity should be O(n x m). But this will probably affected by the domain of the characters in your string.

share|improve this answer
I think I might have misunderstand the question. It want to find the difference of first item from the last row, not from any row. In that case the trie algorithm does not apply. – Wai Yip Tung May 18 '10 at 20:04
Could you expand this answer a little? I currently use Tries for symbol recognition elsewhere in this application but haven't considered how they might help identify images in general since I assumed it would be too slow to derive Tries for images in my future scenarios. – Ed Guiness May 18 '10 at 21:39
I added an example to the answer because I cannot do formatted text in the comment. – Wai Yip Tung May 19 '10 at 0:38
Thanks for expanding. I can see that this would help discover where the strings diverge (branch) but I still can't see how they would help identify all unique charactes and their positions since I would still need to compare the second character of the first branch to the second character of the second branch and so on. Look at my first example to see what I'm after. What am I missing? – Ed Guiness May 19 '10 at 6:32

If your goal is to identify images later, you could create a very fast hash of the image by picking predefined points to serve as identity pixels.

for example, you could have a structure (class, struct, doesn't matter what language) as follows:

structure ImageHash {
    int x_pixels, y_pixels;
    u_long hash;
    void createHash(Image img) {
        x_pixels = img.x_pixels;
        y_pixels = img.y_pixels;
            int x = x_pixels / i;
                int y = y_pixels / j;
                int r = img.getPixelRed(x,y);
                int g = img.getPixelGreen(x,y);
                int b = img.getPixelBlue(x,y);
                hash = (hash * 31) ^ (r^g^b);

This sort of "incomplete hash" will allow you identify possible identities, and then you can do the expensive, full comparison sparingly as required.

Expand the incomplete hash as necessary.

share|improve this answer
+1 creative, although isn't it a catch-22 that I could only choose good predefined points by first identifying those points that are most likely to be unique? – Ed Guiness May 18 '10 at 18:10
I just picked random points. I was going to have them evenly spaced using mod and stuff like that, and then I said meh, these points are valid and "random enough". =) – corsiKa May 18 '10 at 18:13

Your Answer


