PROBLEM LINK:Practice Setter: Aditya Dimri DIFFICULTY:Simple. PREREQUISITES:Basic Data structures. PROBLEM:Given $N$ dishes each represented by a string of lowercase characters, each character representing a different ingredient, find out the number of special ingredients. A special ingredient is an ingredient which is present in all dishes. QUICK EXPLANATION
EXPLANATIONThe problem is really simple. We just need to check for each character from 'a' to 'z' whether this character is present in all strings or not. This can be done in many ways, such as
The method which can be a learning experience is, by using bitmasks. Let us represent each character by a bit. Initially, all bits are set. Now, we represent each string as a bitmask, corresponding bit on for each character present in the string. Can you figure out the bitwise operation required here? Time ComplexityTime complexity is $O(S)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Feb, 23:45
