Counting the gems among the rocks

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase Latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, you have to print how many different kinds of gems-elements he has.

Input Format

The first line consists of N, the number of rocks. Each of the next N lines contain rocks’ composition. Each composition consists of small alphabets of English language.

Output Format

Print the number of different kinds of gem-elements he has.

Constraints

$1 ≤ N ≤ 100$

Each composition consists of only small Latin letters ('a'-'z'). 1 ≤ Length of each composition ≤ 100

Sample Input

3
abcdde
baccd
eeabg

Sample Output

2

Explanation

Only "a", "b" are the two kind of gem-elements, since these characters occur in each of the rocks’ composition.

I tried to solve this HackerRank problem in Java. Do you see any areas for improvement?

public int getGems(List<String> list) {

if (list != null && !(list.size() > 0)) {
throw new IllegalArgumentException("Invalid Input");
}

int gemsCount = 0;
int s = list.size();
int cnt = 1;

// assume list(0) will always have gems
String str = list.get(0);
char[] ch = str.toCharArray();
for (char c : ch) {
for (int i = 1; i < s; i++) {
String st = list.get(i);
if (st.indexOf(c) > -1) {
cnt++;
continue;
} else {
cnt = 1;
break;
}
}
if (cnt == s) {
gemsCount++;
cnt = 1;
}
}
return gemsCount;
}
• You say you've tried to solve the given problem; does the code produce the expected results? Aug 27 '14 at 18:14
• It did not pass all result. Aug 27 '14 at 23:34

I find your variable naming maddening. For example, list is just about the least informative name possible for a list, and str and st are just about the least informative names possible for strings.

The input validation is a bit awkwardly expressed. Also, if list is null, then it will still crash with a NullPointerException.

The comment is a bit misleading.

The many places where you reset cnt make your code hard to follow. Without changing your general strategy too much, here's how you could write it better:

public int getGems(List<String> rocks) {
if (rocks == null || rocks.isEmpty()) {
throw new IllegalArgumentException("No Input");
}

int gemsCount = 0;
int n = rocks.size();

// Use list(0) as a source of candidate gems
char[] candidateGems = rocks.get(0).toCharArray();
for (char c : candidateGems) {
int appearances = 0;
for (String rock : rocks) {
if (rock.indexOf(c) >= 0) {
appearances++;
} else {
break;
}
}
if (appearances == n) {
gemsCount++;
}
}
return gemsCount;
}
• Here char c is going to be compare with even with first rock but since variable appearances is assigned as 0 then it will increment correctly. In my case I was using cnt =1 and comparing with next rock. I will improve myself for naming conventions. Aug 27 '14 at 23:32
• Yes, I've sacrificed a bit of efficiency for readability in the way the first string is processed. You could initialize appearances = 1 instead and start the inner for-loop at the second rock. The important point, though, is that appearances = 1 is only set at one place. Aug 27 '14 at 23:41
• I've improved the naming, but actually, the logic is still wrong. There may be duplicates within candidateGems. Jun 23 '16 at 21:54

You code is cubic in the sense that it has three loops nested:

for (char c : ch) {
for (int i = 1; i < s; i++) {
String st = list.get(i);
if (st.indexOf(c) > -1) {

(note, that st.indexOf(c) is going to loop through the st string to find the char c).

Additionally, as has been pointed out, if the first rock has the same element multiple times, it will cause duplicate counting.

All together though, this creates an $O(b \times i \times g)$ complexity where b is the size of the first rock, i is the number of rocks, and g is the average length of each rock.

Removing the lists brings the process back to not having the indexOf, and replacing it with an indexed lookup (like an array, or bitset) that is indexed on the char value, will bring the problem back to just $O(i \times g)$

There is a trick that makes the system a whole lot faster....

Consider the fact that the input parameters for the challenge are well specified. The inputs are a to z characters. There are just 26 of them.

For brute performance, you can also rely on the fact that an int value in Java has 32 bits.... which is more than 26 letters.

You can prepare an int that has 1-bits set for each character...... and then use bitwise arithmetic to manipulate which elements are in each rock (the unique set), and then bitwise 'and' that with the gems you started with.

I was preparing this answer when this question was closed, so I posted a working implementation of my suggestions as a separate Code Review Question here. Now that this question is again reopened, I am completing my answer here too.

Sets! Sets!

I believe this question was made to test your knowledge of sets. You just have to intersect sets.

public class CountingGems {

public static void main(String[] args) {
Arrays.asList("abcdde", "baccd", "eeabg").stream()
.map(rock -> rock.chars().boxed())
.map(charStream -> charStream.collect(Collectors.toSet()))
.reduce(CountingGems::intersectSets)
.map(Set::size)
.ifPresent(System.out::println);
}

// I don't like the semantics of Set.retainAll, so I wrapped it in an intersect method.
public static <T> Set<T> intersectSets(Set<T> set1, Set<T> set2) {
HashSet<T> outputSet = new HashSet<>(set1);
outputSet.retainAll(set2);
return outputSet;
}
}

Sorry for the Java 8. I realized after writing it that it could be hard to read if you are not familiar with Java 8. The algorithm just intersects each set with the intersection of the previous sets until you get the intersection of all sets.

Your variable names are too short and un-Java-like. I suppose you are coming from another language than Java.

A suggestion for another strategy:

I would recommend Java 8 Lambda expressions and the use of filters, to solve the problem, in a more elegant, and efficient way. Moreover this would work regardless of the N<100 constraint.

public void countGems(List<String> rocks) {
String abcStr = "a b c d e f g h i j k l m n o p q r s t u v w x y z";
List<String> abc = Arrays.asList(abcStr.split(" "));
rocks.stream().filter(item->item.contains(letter)).count()==rocks.size()
).collect(Collectors.toList());

System.out.println("There are " + answer.size() + " gems. The gems are" + answer.toString());
}
1. Make a list of the ABC.
2. Using lambda expressions:

• Filter the abc list as follows:
• For each letter - Look at the list of rocks, filter only the ones that contains the letter "rocks.size()" times (meaning it appears in every rock).

Finally get a filtered list of the gem.

In my opinion, you have misinterpreted the challenge and therefore produced an incorrect solution. An element may appear more than once in a rock, but I believe that it should still only count once. Your code would double-count any element that appears twice in the first rock and that also appears in all subsequent rocks.