First Unique String in an String array

Question

Given a String Array how would you find the first unique String element in the array

public static String UniqueString(String[] s) {

    String str ="";

        for(int i=0;i<s.length;i++) {
            for(int j=i+1;j<s.length;j++) {
                System.out.println(s[i]+" "+s[j]);
                str = s[i];
                if(str==s[j]) {
                   break;
                }

                }if(!(str==s[i+1])){
                    return str;
                }

    }

    return str;
    }

so a String array of {Dog,Cat,Dog,Wolf,lion} would return as Cat

Answer 1

Your approach grows quadratically with the size of the list. There's a better approach that is essentially linear in the list size, which is to use an ordered map from strings to the number of occurrences. Use one pass through the list to build the map and then one pass through the map to find the first element (if any) with a count of 1. You can use a LinkedHashMap to implement this.

public static String uniqueString(String[] list) {
    Integer ZERO = 0; // to avoid repeated autoboxing below
    final LinkedHashMap<String, Integer> map = new LinkedHashMap<>(list.size());

    // build the map
    for (String s : list) {
        Integer count = map.getOrDefault(s, ZERO);
        map.put(s, count + 1);
    }

    // find the first unique entry. Note that set order is deterministic here.
    for (Set.Entry<String, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    // if we get this far, there was no unique string in the list
    return "";
}

Note that you could use any kind of Map implementation (including HashMap) and forgo the ordering property of LinkedHashMap by replacing the second loop with a loop through the original list:

for (String s : list) {
    if (map.get(s) == 1) {
        return s;
    }
}

However, if the list has lots of repeated strings then iterating through the map will probably require significantly fewer iterations. So might as well use the added functionality of LinkedHashMap, which you get for very little performance penalty compared to HashMap.

Answer 2

You were very close to a working solution, you need a flag to indicate whether you found the String again in s (not sure where you got names). Also we compare String(s) with .equals (not ==). And method names start with a lower case letter. Something like,

public static String uniqueString(String[] s) {
    for (int i = 0; i < s.length; i++) {
        boolean unique = true;
        for (int j = i + 1; j < s.length; j++) {
            if (s[j].equals(s[i])) {
                s[j] = s[s.length - 1]; // <-- handle bug, ensure that dupes aren't
                                        // found again.
                unique = false;
                break;
            }
        }
        if (unique) {
            return s[i];
        }
    }
    return "";
}

Answer 3

Java 8

public static String uniqueString(String[] s) {
    StringBuilder result = new StringBuilder();
    Stream.of(s)
            .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
            .entrySet()
            .stream()
            .filter(entry -> entry.getValue() == 1)
            .findFirst()
            .ifPresent(entry -> result.append(entry.getKey()));
    return result.toString();
}

Update, after 2 years:

Not sure why I had used a StringBuilder when I could just do it all in a single statement:

public static String uniqueString(String[] s) {
    return Stream.of(s)
            .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
            .entrySet()
            .stream()
            .filter(entry -> entry.getValue() == 1)
            .findFirst()
            .map(Map.Entry::getKey)
            .orElse(null);
}

Answer 4

Perhaps there is another solution that can also solve your problem in a more java-8 way:

1. using a map to record the count of the duplicated strings and then
2. directly traverse the array from the very beginning till the end and
3. once the string is not duplicated, we get it right there.

That could be like:

public static void main(String... args) {
    String[] arr = {"Dog", "Cat", "Dog", "Wolf", "lion"};
    Map<String, Long> stringCountMap = Arrays.stream(arr)
            .collect(Collectors.groupingBy(s -> s, Collectors.counting()));
    for (String s : arr) {
        if (stringCountMap.get(s) == 1) {
            System.out.println("The first non-duplicate string: " + s);
            break;
        }
    }
}

Also you can turn to LinkedHashMap as others mentioned to keep the order to avoid traverse the original array again as:

private static void another(String[] arr) {
    Map<String, Long> stringCountMap = Arrays.stream(arr)
            .collect(Collectors.groupingBy(s -> s, LinkedHashMap::new, Collectors.counting()));
    for (String s : stringCountMap.keySet()) {
        if (stringCountMap.get(s) == 1) {
            System.out.println("The first non-duplicate string: " + s);
            break;
        }
    }
}

The output will always be:

The first non-duplicate string: Cat

Answer 5

The above answer does not work in all cases. for instance {"Dog","Dog",Cat} would return dog. the problem being that It does not check the entire array for duplicates.

private static String getFirstUniqueString(String[] names) {
    for(int x=0;x<names.length;x++)
    {
        if(countOccurences(names[x],names) == 1 )
            return names[x];
    }
    return "No Unique Strings";
}

private static int countOccurences(String string, String[] names) 
{
    int count=0;
    for(int y = 0; y<names.length;y++)
    {
        if(names[y].equals(string))
        {
            count++;
            if(count >1 )
                return count;
        }
    }
    return count;
}

Instead maybe break it into two pieces. One method to find the unique string the other to count occurrences this way we count exactly how many times the word is mentioned through the entire array. If you simply want to know there more then one and you want to save run time, uncomment the if statement.

Answer 6

public static String FirstUniqueString(String[] strs) {
    List<String> list = new LinkedList<>();
    for (String s: strs) {
        if (list.contains(s)) {
            list.remove(s);
        } else {
            list.add(s);
        }
    }
    return list.get(0);
}

We can use a simple LinkedList to keep a track of the duplicates. For example, if the input is new String[] {Dog, Cat, Dog, Wolf, Lion, Dog}, the first unique element would still be Cat. The list after for-each loop will be in the following sequence: {Cat, Wolf, Lion, Dog}. Big O runtime will be O(N ^ 2) as the for-each loop and contains() requiring O(N) respectively.