How to print unique alphabet from two strings using Java?

Question

Recently, I attended an interview. They asked me to write a program to print unique alphabets and common characters from two strings. I wrote the code below to print the common characters:

String s1 = "I am living in India";
String s2 = "India is a beautiful country";
         
char[] s1Array = s1.toCharArray();
char[] s2Array = s2.toCharArray();

LinkedHashSet<Character> s1CharSet = new LinkedHashSet<Character>();
LinkedHashSet<Character> s2CharSet = new LinkedHashSet<Character>();

for(char kc : s1Array){
    s1CharSet.add(kc);
}
 
for(char c: s2Array){
    s2CharSet.add(c);
}
 
s1CharSet.retainAll(s2CharSet);
 
if(s1CharSet.size()==0){
    System.out.println("There are no common characters between the two strings");
}
else{
    System.out.println(s1CharSet);
}
}

but they said they are not satisfied with my answer. I guess it's because they are not expecting retainAll. So, please tell me the right way of programming to satisfy them in the future.

I even Googled but I didn't find any good, understandable links.

So, how to print unique and common characters from two strings without using retainAll?

Any code would be appreciated.

Answer 1

It is possible the interviewer wanted to check your understanding of the internals of how to solve this problem efficiently, and usage of retainAll() kinda misses the purpose of this task.

To implement it "from scratch" one can use several approaches:

1. Similar to your solution - populate two Set objects - one for each string, and then check the difference/common element between them by:

   for (Character c : set1) {
       if (set2.contains(c)) {
           System.out.println(c);
       }
   }
   

   You can even use a bitset if the alphabet is known to be constant (and small enough), otherwise a HashSet is fine and will achieve O(n) average case performance.

2. sort and iterate: sort the two char arrays and iterate together to find common (and unique) characters. While in java there is no real benefit for it (since String is immutable, so you need to create a new char[] anyway) - in other languages, it saves up space and can be done inplace with really little additional space.

Answer 2

when you are going for an interview and if they ask a silly question like the one you said, then they are not looking for a complex Collection framework. They are looking if you can do the same at the grass root level with your coding abilities keeping in mind how you write a code that will be able to handle cases even if the data provided goes into millions.

This problem can be easily solved by taking a byte[]. We know that char is represented by numeric internally.

so in the first iteration, just iterate over the chars of the first string(str1) and set the byte location to some constant, say 1.

for (int i=0; i<str1.length; i++) {
     byteArr[(int)str.charAt(i)] = 1; // O(1)
}

so in the second iteration, just iterate over the chars of the second string and set the byte location to some constant say 2 only if it is set to 1, and 3 to represent that it is unique to str2.

In the third iteration, just iterate over the byte arr and print the chars(convert the index to char) where ever it is 2 for common and 1/3 for unique.

final solution O(n) and scalable.

Answer 3

Print unique and common characters from two strings without using retainAll.

String firstString = "I am living in India";
String secondString = "India is a beautiful country";

HashSet<Character> h1 = new HashSet<Character>(), h2 = new HashSet<Character>();
for(int i = 0; i < firstString.length(); i++) {
    h1.add(firstString.charAt(i));
}
for(int i = 0; i < secondString.length(); i++){
    h2.add(secondString.charAt(i));
}

StringBuffer commonSB = new StringBuffer();
StringBuffer uniqueSB = new StringBuffer();

for(Character i : h1){
    if(!h2.contains(i)){
       uniqueSB.append(i);
    }else{
       commonSB.append(i);
    };
 }
   
 for(Character i : h2){
    if(!h1.contains(i)){
       uniqueSB.append(i);
    };
 }

 System.out.println("Common:"+commonSB.toString().replace(" ", ""); 
 System.out.println("Unique:"+uniqueSB.toString().replace(" ", "");

Results:

Common:danli
Unique:gvmIfebcoutsry

Answer 4

s1CharSet.retainAll(s2CharSet);

Seems like the above line just gave the intersection (A intersection B).

To get all the Unique characcrters you need to get the UNION. A-B + A Intersection B + B-A.

UPDATE: Reference :Intersect and Union

public class Test {

public static void main(String... args) throws Exception {

    List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
    List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

    System.out.println(new Test().intersection(list1, list2));
    System.out.println(new Test().union(list1, list2));
}

public <T> List<T> union(List<T> list1, List<T> list2) {
    Set<T> set = new HashSet<T>();

    set.addAll(list1);
    set.addAll(list2);

    return new ArrayList<T>(set);
}

public <T> List<T> intersection(List<T> list1, List<T> list2) {
    List<T> list = new ArrayList<T>();

    for (T t : list1) {
        if(list2.contains(t)) {
            list.add(t);
        }
    }

    return list;
}
   }

Answer 5

I would have done something like:

//assume questions treats I and i as the same.
    String s1 = "I am living in india".toLowerCase();
    String s2 = "india is a beautiful country".toLowerCase();

    //Since character is comparable this will maintain the set in alphabetical order when we print it. - well based on the numerical chacacter anyway.
    Set<Character> unique = new TreeSet<Character>(); 
    Set<Character> common = new TreeSet<Character>();

    unique.addAll(Arrays.<Character>asList(ArrayUtils.toObject(s1.toCharArray()))); //Oh java !?!?!
    for(Character c : s2.toCharArray()){
        if(!unique.add(c)){
            common.add(c);
        }
    }

    //Assume question didnt mean to include whitespace
    unique.remove(' ');
    common.remove(' ');

    System.out.println("Unique: " + unique.toString());
    System.out.println("Common: " + common.toString());

This basically just exploits the behaviour of the set add function, that it returns true if the element was not in the set, and false if it was. The set avoids duplication.

Gives the output:

Unique: [a, b, c, d, e, f, g, i, l, m, n, o, r, s, t, u, v, y]
Common: [a, d, i, l, n, t, u]

There are a couple of small points that an interviewer might pick up on:

1) You used the class and not the interface in your LinkedHashSet definitions. This is widely regarded as bad practice and might be taken as showing that you have limited familiarity with Java - ofc, whether that is an issue depends on what level of experience they are interested in..

2) Your variable naming. You are never happy as an interviewer if your candidate keeps naming objects "thingy" or functions "someFunction", a natural programmer produces helpful names for objects and functions on the fly. Again, depending on the level of experience they wanted this might or might not be an issue.

3) They might have been looking for some imagination in interpreting the question, e.g. to ask if whitespace was a "character" in the question, or to sort the output to make it more readable. Or to ask whether to treat I and i as the same or different characters.

4) They might have been expecting some knowledge of the timeline of Java development, e.g. to say "Here I used Autoboxing, so it requires a 1.7 or later compiler."

5) You might just have taken too long, or needed too many syntax hints/corrections.

Answer 6

class uniqueCharInTwoString{
    public static void unique(String a, String b){
        HashSet<Character> unique = new HashSet<Character>();
        HashSet<Character> common = new HashSet<Character>();
        for(Character c : a.toCharArray()){
            unique.add(c);
        }
        for(Character c : b.toCharArray()){
            if(!unique.add(c)){
                common.add(c);
            }
        }
        unique.removeAll(common);
        unique.remove(' ');
        common.remove(' ');
        System.out.println(unique);
        System.out.println(common);
    }
    public static void main(String args[]){
        String a = "abdedf";
        String b = "cdfang";
        unique(a,b);
    }
}

Answer 7

This is my solution for implementing LinkedHashSet to maintain character order in the strings.

import java.util.LinkedHashSet;
import java.util.Set;

public class CommonCharacters {
 public static void main(String[] args) {
    Pair<String, String> p = getDuplicates("abdxzewxk", "axzmnx");
    System.out.println("Unique:" + p.value1 + "  Common:" + p.value2);
}

public static Pair<String, String> getDuplicates(String s1, String s2) 
{
    Set<Character> xters1 = new LinkedHashSet<Character>();
    Set<Character> xters2 = new LinkedHashSet<Character>();

    for (char c : s1.toCharArray()) {
        xters1.add(c);
    }

    for (char c : s2.toCharArray()) {
        xters2.add(c);
    }

    Set<Character> unique = new LinkedHashSet<>();
    Set<Character> common = new LinkedHashSet<>();

    for (char c : xters1) {
        if (xters2.contains(c))
            common.add(c);
        else
            unique.add(c);
    }

    for (char c : xters2) {
        if (xters1.contains(c))
            common.add(c);
        else
            unique.add(c);
    }

    return new Pair(stringfry(common), stringfry(unique));
}

public static String stringfry(Set<Character> chrs) {
    StringBuilder sb = new StringBuilder();
    chrs.forEach(s -> {
        sb.append(s);
    });
    return sb.toString();
}


static class Pair<E, U> {
    private E value1;
    private U value2;

    public Pair(E value1, U value2) {
        this.value1 = value1;
        this.value2 = value2;
    }
}

Answer 8

Let's say for simplicity our strings only consist of lower case characters. Now we can construct two arrays of length 26, and count the occurrence of characters. Now compare both arrays, if both have count >0, then it's common to both strings. If the count is zero in one and non-zero in another, it is unique to that particular string. If both are zero the character is not present in either string.

The above approach could be used for many similar problems.

Answer 9

Print out all the Common Characters:

public class Test10 {
    public static void main(String[] args) {
        String a = "Gini Gina Protijayi".toLowerCase();
        String b = "Soudipta".toLowerCase();
        // print out all the common characters
        a.chars()
        .distinct()
        .mapToObj(ch -> String.valueOf((char) ch))
        .filter(b::contains)
        .forEach(System.out::println);

    }// main
}

Answer 10

Try this code with your inputs, you will get the result you need.

import java.util.HashSet;

  public class Practice {
        public static void main(String[] args) {
        String str1 = "Ro is Captain";
        String str2 = "Ri is keeper";

        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();`enter code here`

        HashSet hs = new HashSet();
        HashSet hf = new HashSet();
        HashSet hx = new HashSet();
        for (int i = 0; i < c1.length; i++) {
            hs.add(c1[i]);
        }
        for (int i = 0; i < c2.length; i++) {
            hs.add(c2[i]);
        }
        for (int i = 0; i < c1.length; i++) {
            hx.add(c1[i]);
        }
        for (int i = 0; i < c2.length; i++) {
            hf.add(c2[i]);
        }
        hx.retainAll(hf);
        hs.removeAll(hx);

        System.out.println("Uncommon Chars : " + hs);
    }
}