To address the problem of generating an array of words where each word appears exactly once in the input array while preserving their original order, we can utilize a frequency-counting approach with a HashMap and a single traversal. Here’s a clean, efficient, and self-contained Java solution:

When working with arrays of strings, a common requirement is to remove duplicate entries while maintaining their original order of first occurrence. This problem is essential in various applications like data cleansing, generating unique lists from user inputs, or efficiently handling large datasets. Here, we present a clean and efficient solution using a HashMap to achieve this in linear time with single traversal.

Problem Statement

Given an array of words, we need to generate a new array where each word appears exactly once, preserving the order as they first appeared in the input. For example:
text
Input: ["apple", "banana", "apple", "orange", "banana", "kiwi"]
Output: ["apple", "banana", "orange", "kiwi"]

Approach

To solve this problem efficiently, we can leverage a HashMap to track seen words in a single pass. Here’s the step-by-step strategy:

1. Initialize Data Structures:

   • A Map<String, Boolean> to track whether a word has already been encountered.
   • An ArrayList<String> to store the ordered unique words.

2. Traverse the Input Array:

   • For each word, check if it is present in the map.
   • If not present, add it to the map and the result list.

3. Convert the List to an Array:

   • Finally, return the list converted back to a String[].

This approach ensures O(n) time complexity, as each element is processed once with O(1) hash map lookups and insertions. The space complexity is O(n), as in the worst case all words are unique.

Java Implementation

java
import java.util.*;

public class UniqueWordExtractor {
public static String[] removeDuplicates(String[] input) {
// Handle edge cases
if (input == null || input.length == 0) {
return new String[0];
}

    Map<String, Boolean> seen = new HashMap<>();

    List<String> result = new ArrayList<>();
for (String word : input) {

        if (!seen.containsKey(word)) {

            seen.put(word, true); // Mark as seen

            result.add(word);     // Add to unique list

        }

    }
return result.toArray(new String[0]); // Convert to array

}
// Example usage

public static void main(String[] args) {

    String[] input = {"apple", "banana", "apple", "orange", "banana", "kiwi"};

    String[] output = removeDuplicates(input);
System.out.println(Arrays.toString(output));  // ["apple", "banana", "orange", "kiwi"]

}

}

Explanation

• HashMap Usage:

  • The HashMap stores unique words as keys, with values set to true to denote their first occurrence. This allows O(1) time checks for whether a word has been seen.

• Order Preservation:

  • Since elements are added to the ArrayList only when first encountered, the order matches their original appearance in the input array.

• Efficiency:

  • Each array element is processed once (O(n) time).
  • No nested loops, making this scalable for large datasets.

Comparison with Alternative Approaches

While a LinkedHashSet can achieve the same result in fewer lines, this explicit HashMap-based method provides clarity on how insertion order and uniqueness are managed. It is also adaptable to variations of the problem, such as filtering words based on frequency (e.g., retaining only words that appear exactly once).

An alternative using LinkedHashSet would look like this:
java
public static String[] removeDuplicates(String[] input) {
if (input == null || input.length == 0) {
return new String[0];
}

Set<String> set = new LinkedHashSet<>(Arrays.asList(input));

return set.toArray(new String[0]);

}

This method internally handles ordering and uniqueness, but the original approach is more instructive for understanding underlying mechanics.

Edge Cases

• Empty or null input: Handled by returning an empty array.
• All duplicates: Returns a single-element array.
• Single element: Returns the original array.
• Mixed case: Case-sensitive (requires modification for case-insensitive handling).

Conclusion

The HashMap-based solution effectively addresses the problem with optimal performance and simplicity. By leveraging a single pass through the input and O(1) hash lookups, it guarantees both time and space efficiency. This method is a foundational algorithm useful in many data-processing scenarios and provides a clear lens into managing unique entries in sequential structures.