1

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?

Improve this question
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.

Improve this answer
4
  • Imagine that the first string has only one character, and the second line is long and contains all sizeof(char_t) * 8 possible characters. You'd have counted great many counts of characters in the second string that don't ever occur in the first. (This, or I misunderstand what you mean saying "preprocess both strings"). – 9000 Oct 22 '14 at 19:22
  • I was thinking p = string1; while(c=*p) {count1[c]++;} then same thing for string2. – Jeff Bell Oct 22 '14 at 19:55
  • Well, this can make perfect sense if we use byte-sized characters. – 9000 Oct 22 '14 at 20:59
  • hmm i am not using c++ though was looking to approach this using pure c... – user2733436 Oct 23 '14 at 12:51
0

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.

Improve this answer
1
  • I like you're approach would it work if i had more then 2 strings i could have n strings in the array...and i am using pure c not c++ to solve this – user2733436 Oct 23 '14 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.