CareerCup

Commenting on the solution on the top by Saurabh. Originally I arrived at a similar solution by storing all duplicates and removing them from the final list. However I then corrected my solution to avoid 'transitive' removal of contacts. Consider the following example of contacts:
1 a b
2 b c
3 c d

The solution above will remove all of the contactIDs and return an empty set, because the second contactD has one 'email' in common with the first contactID ('b'), and the third contactID has one 'email' in common with the second contactID ('c'). This solution above marks all contactIDs as duplicates.

However I think removing duplicates means you remove just contactIDs that are duplicate with some other contactID that will remain in the output not those that were duplicate with the removed one. So I think the correct outputs are the following:
{1, 3}

(OR also {2, 3} and {1, 2} if order of the input does not matter)

ContactIDs 1 and 3 have no email in common so they should not be removed. Part of my code doing this is below. It only adds the emails of a contactID into the tracking list if the contactID is not removed:

for(String contact : listOfContacts.keySet()){
            boolean toBeRemovedFlag = false;
            for(String email : listOfContacts.get(contact)){
                if(emailsAll.containsKey(email)){
                    toBeRemoved.add(contact);
                    toBeRemovedFlag = true;
                    break;
                }
            }
            if(!toBeRemovedFlag){
                for(String email : listOfContacts.get(contact)){
                    if(emailsAll.containsKey(email)){
                        emailsAll.put(email, emailsAll.get(email) + 1);
                    } else {
                        emailsAll.put(email, 1);
                    }
                }
            }
        }

What do you think, which approach is correct?

Inspired by @dmitry.labutin this is a Java version of that solution:

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class Solution{
    public List<String> patterns(Map<String,String[]> m, String str) {
        List<String> res = new ArrayList<String>();
        if (str.length() == 0){
            return res;
        }
        for (String k : m.keySet()) {
            if (str.startsWith(k)) {
                for(String kv : m.get(k)) {
                    String strSubstr = str.substring(k.length());
                    if((strSubstr.length() == 0)) res.add(kv);
                    else {
                        List<String> ends = patterns(m, strSubstr);
                        for (String e : ends) {
                            res.add(kv+e);
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Map<String, String[]> m1 = new HashMap<String, String[]>();
        m1.put("1", new String[]{"A","B","C"});
        m1.put("2", new String[]{"D","E"});
        m1.put("12", new String[]{"X"});
        m1.put("3", new String[]{"P","Q"});

        Solution sol = new Solution();
        List<String> out = sol.patterns(m1,  "123");
        for(String s : out){
            System.out.println(s);
        }
    }
}