This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.
Consider how you could use a Map (for your purposes, a java.util.LinkedHashMap would be a wise choice) to store the relationship between the first and second strings. Since a Map automatically eliminates duplicate keys, and since LinkedHashMap stores the keys in insertion order, it would do virtually all of the work for you. You'd just add all the pairs, allocate new arrays the same size as the map, then iterate over the map and populate the two arrays.