Heres some starter code to get you started:

class Pair{

private int count;

private int index;

// YOUR CODE HERE

// Write getters and setters

}

class MinHeap {

public int extractMin(){

//YOUR CODE HERE

}

public void insert(...) {

//YOUR CODE HERE

}

public void minHeapify(...) {

// YOUR CODE HERE

}

}

public class AlienDecoder {

public void decodeMessage(String message, int k) {

// traverse string and build a map (ok to use collection here)

// traverse map and build heap with the relevant characters

// Extract k characters from the heap and print them in the same order.

}

public static void main(String[] args) {

// accept the string and k from the command line

// (either as arguments or otherwise

AlienDecoder adObject;

adObject.decodeMessage(...);

}

}

An "easy" approach would be as follows - Store each character's count in a map/array by traversing it once. Then traverse the string once more to find the first k characters having their count as 1 . The problem is that once you have read the string(input message), it will self-destroy and won't be available for further processing. Instead, you come up with a clever alternative. You build a map to store the count of characters and the index of the first and/or last occurrence of the character. Then go through the map and insert the index of all the characters that have a character count of 1 , into a min-heap. A minheap is similar to a max-heap that you learnt in class, but the smallest number is always at the root and the parent is smaller than both the children. Finally pop the first k values from this minheap. Example: Input string: BBCISISAGOODDOGTOO Output: message is CAT Additional instructions: 1. Do not use PriorityQueue from java collections and write your own buildHeap and minHeapify and extractmin. Use an array based heap implementation 2. Use simple arrays to store the heap. (think about what the array would actually contain) 3. Write test cases to make sure that your code is working well. Write them in a separate file named AlienDecoderTest.java using Junit. 4. Generate your own string sequences. (you may do this in main if you want)