programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Tim Cooke
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Knute Snortum
• paul wheaton
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Ron McLeod
• Piet Souris
• Ganesh Patekar
Bartenders:
• Tim Holloway
• Carey Brown
• salvin francis

# Finding common characters of two strings in O(n)

Ranch Hand
Posts: 103
Hi,
The following code I have written to find common characters between two strings.Can we do it in a better way but within linear time?

Regards,
Arka

Ranch Hand
Posts: 287

Marshal
Posts: 65413
248
It all depends what you mean by common characters. Do “CAMPBELL” and “RITCHIE” have C and E as common characters because C and E both appear? Or do they have no common characters because the first two characters are different, the second two different, etc. In the latter case “three” and “ether” would have one e in common, as the 4th character, which can be found as pairs in linear time by iterating the String. If you use the set solution above, you will get 4 duplicates: ehrt, because those two words are anagrams of each other.

But that Set thing is a good solution, which will also run in linear time.

Bartender
Posts: 10777
71
Just a small point: if Harsha's solution was changed to use LinkedHashSet's, it's likely that the original character order would be retained in the resulting Set, admittedly at a small (but linear) cost in speed.

Winston

Campbell Ritchie
Marshal
Posts: 65413
248
Good idea; you would get t-h-r-e from three and e-t-h-r from ether.

 A feeble attempt to tell you about our stuff that makes us money Enterprise-grade Excel API for Java https://products.aspose.com/cells/java