Creating a List of Non-Repeated characters from the given Array of characters

Question

I found that on execution line nonReps.remove(indexInNonreps); doesn't removing the object at the specified index.

Why does it happen?

My code:

 // given an array
Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};


Map<Character, Integer> map = new HashMap<>();
List<Character> nonReps = new ArrayList<>();

for (int i = 0; i < arr.length; i++) {
    if (map.containsKey(arr[i])) {
        Integer indexInNonreps = map.get(arr[i]);
        Character characterInNonreps = nonReps.get(indexInNonreps);

        if (arr[i].equals(characterInNonreps))
            nonReps.remove(indexInNonreps);
        } else {
            nonReps.add(arr[i]);
            map.put(arr[i],nonReps.size()-1);
        }
    }
}

System.out.println(nonReps);

The code prints:

[a, b, c, d, e, f]

Expected:

[b, d, f]

`nonReps.remove(indexInNonreps);` <- this is calling the `boolean java.util.List.remove(Object o)` method because you are using `Integer`. If you want to call the remove method that takes an `int` as index you should do `nonReps.remove(indexInNonreps.intValue());` — OH GOD SPIDERS, Jul 22 '22 at 15:20
'a','a','a', --> logic is written in a way, that for 1st entry, list has `a`, for second `a`, it got removed, for third it again got added `a`. & that is reason you are getting `[a, b, c, d, e, f]`. Because I think question is asked for that? — Ashish Patil, Jul 22 '22 at 15:51
@AshishPatil the answer of "OH GOD SPIDERS" was the one I needed. I did not realize the remove() method was overloaded. By the way, after fixing this error I had to change the logic a little bit — Arlex, Jul 22 '22 at 16:16

Alexander Ivanchenko · Answer 1 · 2022-07-23T03:33:32.393

As OH GOD SPIDERS has pointed out in the comments there are two flavors of remove() method available in the List interface:

remove(Object o) - inherited from the Collection interface, which expects an object to remove as parameter.
remove(int index) - defined by the List interface, which expects the index of the element to be removed.

The compiler maps each method call to the most specific method (if there are some overloaded versions) based on the types of arguments, which in the case of nonReps.remove(indexInNonreps) happens to be remove(Object) because indexInNonreps is of type Integer.

If you unbox the indexInNonreps into primitive int you would face another issue - IndexOutOfBoundsException because right after the first removal, indices in the List would no longer match the indices in the Map.

To avoid this problem and to improve the performance (removal of an arbitrary element by index from a List is constful - in case of ArrayList all elements to right from the removed one need to be shifted, in the LinkedList you first need to find the target element by iterating over the list, it gives a time complexity of O(n), the same applies for removing a particular object from a list) we can firstly generate a Map which would indicate whether a particular character is repeated or not. And then construct a List of non-repeated characters.

That's how it might be done in O(n) time and using as fewer code as possible:

Map<Character, Boolean> isNonRepeatedByChar = new LinkedHashMap<>();

for (Character next : arr) {
//  isNonRepeatedByChar.merge(next, true, (v1, v2) -> false); // does the same as to lines below

    isNonRepeatedByChar.replace(next, true, false); // the key has been already encountered - changing value to false
    isNonRepeatedByChar.putIfAbsent(next, true);    // the key has NEVER been encountered before - adding the entry with value of true
}

List<Character> nonReps = new ArrayList<>();

for (Map.Entry<Character, Boolean> entry : isNonRepeatedByChar.entrySet()) {
    if (entry.getValue()) nonReps.add(entry.getKey());
}

System.out.println(nonReps);

Output:

[b, d, f]

Note: I've used a LinkedHashMap assuming that preserving the initial order of elements is important. If it's not the case - go with a plain HashMap.

In case if you're comfortable with streams you can obtain the result in a single statement:

List<Character> nonReps = Arrays.stream(arr)
    .collect(Collectors.toMap(
        Function.identity(),
        ch -> true,             // the key has NEVER been encountered before - adding the entry with value of true (i.e. non-repeated)
        (v1, v2) -> false,      // the key has been already encountered - changing value to false
        LinkedHashMap::new
    ))
    .entrySet().stream()
    .filter(Map.Entry::getValue)
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

Thank you for your answer, after OH GOD SPIDERS pointed the issue, I encountered the indexOutOfBounds and fixed it. However, I did not use LinkedHashMap, I guess I need to study further. Thank you as well for including the streams solution, I was wondering if there was a way with it, I am still in learning process. What I do not understand is in the second part of the statement, when you get the Values from the filter, how does it know that it should take only the True values? — Arlex, Jul 22 '22 at 22:22
@Arlex `LinkedHashMap` maintains a Linked List under the hood to preserve the order of entries, and that's how it differs from `HashMap`. When you iterate over the entries of `LinkedHashMap` the entries would be retrieved strictly in the order they were added. But it has an additional cost, hence if you are not interested in the order use a regular `HashMap`. — Alexander Ivanchenko, Jul 22 '22 at 22:28
@Arlex `second part of the statement, when you get the Values from the filter` - collector `toMap` creates an intermediate `Map`. Value denotes whether the character is not repeated. `filter()` takes a Predicate as an argument and preserves in the stream only those elements for which the *predicate* would be evaluated to `true` (not the opposite). So `filter(Map.Entry::getValue)` means - give me the entries having the value of `true` (reminder value is of type `Boolean` here). — Alexander Ivanchenko, Jul 22 '22 at 22:37
@Arlex If you're confused with the syntax `Map.Entry::getValue`, it's called Method reference - https://docs.oracle.com/javase/tutorial/java/javaOO/methodreferences.html — Alexander Ivanchenko, Jul 22 '22 at 22:37
Thank you very much @Alexander, I know understood everything. I am still new with streams and forgot filter takes a predicate. — Arlex, Jul 22 '22 at 22:47

score 0 · Answer 2 · answered Jul 22 '22 at 17:11

You can use Set to check if the character is unique or not, if not delete from noReps

    public static void main(String[] args) {
        Character[] arr = new Character[]{'a','a','a','b','c','c','c','d','e','e','e','f'};

        Set<Character> seen = new HashSet<>();
        List<Character> nonReps = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            if(seen.contains(arr[i])){
                nonReps.remove(arr[i]);
            }else{
                nonReps.add(arr[i]);
                seen.add(arr[i]);
            }
        }
        System.out.println(nonReps);
    }

, output

[b, d, f]

Creating a List of Non-Repeated characters from the given Array of characters

2 Answers2