You are not logged in. Please login at www.codechef.com to post your questions!

×

# CHEFING - EDITORIAL

Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

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?

View Content

# Time Complexity

Time complexity is $O(|S|)$ per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Feb, 23:45

4.0k31103
accept rate: 22%

19.8k350498541

 0 btw I get AccessDenied if I click on solutions answered 17 Feb, 02:07 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×1,409
×1,191
×643
×185
×8

question asked: 13 Feb, 23:45

question was seen: 509 times

last updated: 17 Feb, 02:07