PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Aditya Dimri
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh
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
- Initially, all characters are considered special.
- For every string, we can mark the characters not present in the string as non-special. Hence, the characters marked special after considering all strings are the required set of characters.
EXPLANATION
The 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
- For each character, iterate over all strings and check if this character is present in all strings. If yes, increment the answer by one. The final value of the answer is the number of special ingredients.
- Maintain a special integer array of size A being the size of the alphabet, and for every unique occurrence of a character in the string, increase the character position in the array by one. The final answer is the number of characters, which have special array value equal to N.
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?
Click to view
We need to preserve only the bits which are set in both masks. This is what AND operation does.
Time Complexity
Time complexity is O(|S|) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 