Return equal occurrence of char in a list of strings

Question

I have an array of strings ["abb", "bbxxaa"].

I would like to print all characters that occur equal times in each index so in above case I would print bb because they occur twice in both indexes and a occurs once and twice in first and second index respectively.

My approach:

Keep track of only the characters in the first index and because we would not need to worry about other letters anyway. So in above case I would keep track of letter a and b and check if they occur same time in the next indexes.

Can someone suggest a better way if possible or am I on right track?

Answer 1

You are off to a good start but you might want to consider how it performs when these strings are long. For each letter in the first string you could end up comparing against every letter in the second string, taking time that grows as the product of the two string sizes.

One way would be to preprocess both strings so that for a given letter you know how many times it happens. If you are sure that these are 8 bit characters, you could use two int arrays of size 256, if you make sure to reset them to zero. (in c++ it might be easier to build a character to int map.) For output you loop up the count of each character in your table, and see if it had the same count in the other table.

A slightly different way would be to sort each string. Then you could scan forward through both sorted strings at the same time.

Answer 2

Only tracking characters from the first string is a good idea.

You can also stop tracking characters once you've proven that there are more such characters in the second string than in the first.

So I'd keep a list of structs {char_t character, int count_first, int count_second} for each distinct character of first string. For each character in the second string, I'd scan the list and increment the count_second in the element where character matches the current character. If count_first < count_second after this, I'd remove the element from the list.

In the end, I'd filter the elements where count_first == count_second.