Get the Strings that occur exactly three times from Arraylist

Question

I have an ArrayList which contains some values with duplicates and elements that occur thrice, I want to collect those values that occur thrice specifically into another ArrayList like

Arraylist<String> strings;   //contains all strings that are duplicates and that occur thrice

Here, I want to get only the Strings that occur thrice in another array list.

Arraylist<String> thrice;    //contains only elements that occur three times.

Currently, I have a solution for dealing with duplicates but I cannot extend this for only getting strings that occur thrice, this please help me to find out.

Basically, instead of using a **HashSet** you now want to use a **HashMap** to count the number of occurrences of each string. — Sash Sinha, Jan 02 '19 at 16:31
See [this answer](https://stackoverflow.com/questions/27254302/counting-duplicate-values-in-hashmap) for a solution as @shash678 suggested — Stalemate Of Tuning, Jan 02 '19 at 16:35
Possible duplicate of [get the duplicates values from Arraylist and then get those items in another Arraylist](https://stackoverflow.com/questions/54007206/get-the-duplicates-values-from-arrayliststring-and-then-get-those-items-in-ano) — , Jan 04 '19 at 17:25

Ousmane D. · Answer 1 · 2019-01-02T16:51:39.090

3

You can do it via a stream as follows:

 List<String> result = strings.stream()
                .collect(Collectors.groupingBy(Function.identity(), counting()))
                .entrySet().stream()
                .filter(e -> e.getValue() == 3) // keep only elements that occur 3 times
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());

You could also do it as follows, but I'd recommend the above as it's more preferable.

List<String> result = new HashSet<>(strings).stream()
                            .filter(item -> strings.stream()
                                  .filter(e -> e.equals(item)).limit(3).count() == 3)
                          .collect(Collectors.toList());

edited Jan 02 '19 at 16:51

answered Jan 02 '19 at 16:36

Ousmane D.

54,915
8
91
126

1

The second one doesn't seem really efficient, it has a O(n^2) time complexity for a problem which is easily solved in O(n), kind of overkill. – Ricola Jan 02 '19 at 16:47
@Ricola First is definitely preferable. I'll edit to explicitly say so. – Ousmane D. Jan 02 '19 at 16:49

Sash Sinha · Answer 2 · 2019-01-04T14:54:15.723

Basically, instead of using a HashSet you now want to use a HashMap to count the number of occurrences of each string.

Furthermore, instead of writing a method for finding the strings that occur three times specifically, you could write a method that takes in a parameter, n and finds the strings that occur N times:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class StackOverflowQ {

  static List<String> getStringsThatOccurNTimes(List<String> stringList, int n) {
    if (stringList == null || stringList.size() == 0) {
      return stringList;
    }
    Set<String> stringsThatOccurNTimesSet = new HashSet<>();
    Map<String, Integer> stringCounts = new HashMap<>();
    for (String s : stringList) {
      int currentStringCount = stringCounts.getOrDefault(s, 0) + 1;
      stringCounts.put(s, currentStringCount);
      if (currentStringCount == n) {
        stringsThatOccurNTimesSet.add(s);
      } else if (currentStringCount == n + 1) {
        stringsThatOccurNTimesSet.remove(s); // We use a set so this operation is O(1)
      }
    }
    return new ArrayList<>(stringsThatOccurNTimesSet);
  }

  public static void main(String[] args) {
    List<String> stringsList = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e", "b", "c", "c", "d", "d", "d", "e"));
    List<String> stringsThatOccurTwoTimes = getStringsThatOccurNTimes(stringsList, 2);
    List<String> stringsThatOccurThreeTimes = getStringsThatOccurNTimes(stringsList, 3);
    List<String> stringsThatOccurFourTimes = getStringsThatOccurNTimes(stringsList, 4);
    System.out.println("Original list: " + stringsList);
    System.out.println("Strings that occur two times: " + stringsThatOccurTwoTimes);
    System.out.println("Strings that occur three times: " + stringsThatOccurThreeTimes);
    System.out.println("Strings that occur four times: " + stringsThatOccurFourTimes);
  }

}

Output:

Original list: [a, b, c, d, e, b, c, c, d, d, d, e]
Strings that occur two times: [b, e]
Strings that occur three times: [c]
Strings that occur four times: [d]

How [about a util](https://stackoverflow.com/a/54010424/1746118) for this in general? — Naman, Jan 02 '19 at 17:13
Nice I use something similar in python when I do interview questions that are similar to OP's one. — Sash Sinha, Jan 02 '19 at 17:28

score 0 · Answer 3 · answered Jan 02 '19 at 17:06

You can use computeIfAbsent for this.

List<String> strings;

final Map<String, BigInteger> stringCounts = new HashMap<>();
strings.stream().forEach(s -> {
  BigInteger count = stringCounts.computeIfAbsent(s, k -> BigInteger.ZERO).add(BigInteger.ONE);
  stringCounts.put(s, count);
});

Now filter stringCounts with value=3.

Naman · Accepted Answer · 2019-01-02T17:37:47.620

A generic utility of what you're trying to acheieve in both the questions would be using Collections.frequency as :

/**
 * @param input the list as your input
 * @param n number of occurrence (duplicates:2 , triplets:3 etc..)
 * @param <T> (type of elements)
 * @return elements with such conditional occurrent in a Set
 */
static <T> Set<T> findElementsWithNOccurrence(List<T> input, int n) {
    return input.stream()
            .filter(a -> Collections.frequency(input, a) == n) // filter by number of occurrences
            .collect(Collectors.toSet()); // collecting to a final set (one representation of each)
}

Note: This would be an O(n^2) approach since its using Collections.frequency which iterates over the entire collection again to get the frequency. But proposed for a more readable and generic approach towards what you're looking for. Also, this intentionally collects final output to a Set, since a List can again have duplicates after all.

Alternatively, you can use the method to count the frequency of elements in Java-8 and iterate over the entries of the Map created thereby to process filtering as desired and collect the output in the same iteration :

/**
 * @param input the list as your input
 * @param n     number of occurrence (duplicates :2 , triplets :3 etc)
 * @param <T>   (type of elements)
 * @return elements in a set
 */
static <T> Set<T> findElementsWithNOccurrence(List<T> input, int n) {
    return input.stream() // Stream<T>
            .collect(Collectors.groupingBy(Function.identity(), 
                    Collectors.counting())) // Map<T, Long>
            .entrySet() // Set<Map.Entry<T,Long>>
            .stream() // Stream<Map.Entry<T,Long>>
            .filter(e -> e.getValue() == n) // filtered with frequency 'n'
            .map(Map.Entry::getKey) // Stream<T>
            .collect(Collectors.toSet()); // collect to Set
}

score 0 · Answer 5 · answered Jan 05 '19 at 07:10

The best way to do this is.....

Making of required arraylist.........

    ArrayList<String> thrice=new ArrayList<>();
    ArrayList<String> one=new ArrayList<>();

Adding some values for checking.......

    one.add("1");one.add("1");one.add("1");one.add("1");one.add("1");
    one.add("2");one.add("2");one.add("2");one.add("2");one.add("2");
    one.add("1");one.add("1");one.add("1");
    one.add("3");one.add("3");
    one.add("4");one.add("5");
    one.add("2");one.add("2");one.add("2");

Mapping to done the task.....

    Map<String, Integer> duplicates = new HashMap<String, Integer>();

    for (String str : one) {
        if (duplicates.containsKey(str)) {
            duplicates.put(str, duplicates.get(str) + 1);
        } else {
            duplicates.put(str, 1);
        }
    }

    for (Map.Entry<String, Integer> entry : duplicates.entrySet()) {

                       if(entry.getValue()>=3){
                             thrice.add(entry.getKey());
                           }
    }

Set the list in listview...

    ArrayAdapter<String> ad=new ArrayAdapter<> 
    (this,android.R.layout.simple_list_item_1,thrice);
    ListView lv=findViewById(R.id.new_l);
    lv.setAdapter(ad);

Output= 1,2

Already check the answer and you can change the condition according to your way

                           if(entry.getValue()>=3){
                             thrice.add(entry.getKey());
                           }

Easiest answer from above...not required to change the versions of minimum sdk for android user

Get the Strings that occur exactly three times from Arraylist

5 Answers5

Linked