Cops and robbers program to find the most frequent character in a string

Question

I made this program to train me for a competition. The hypothetical question I've used was

The cops need help finding who is the most probable criminal to commit a crime. Witnesses tell them multiple different people, making it hard to find the criminal. Use your knowledge of coding and the one-letter identifications provided for the criminals to find who most likely did it and print.

It was fun making the code; however, it felt like it took too long for such a simple code. Is there any way to make this simpler or better?

import java.util.*;
public class CopsAndRobbers {
 public static void main(String[] args) {
 //The cops need help finding who is the most probable criminal to commit a crime
 //Witnesses tell them multiple different people, making it hard to find the criminal
 //Use your knowledge of coding and the one-letter identifications provided for the criminals
 //To find who most likely did it and print.
 TreeSet<String> done = new TreeSet<String>();
 ArrayList<String> all = new ArrayList<String>();
 ArrayList<Integer> num = new ArrayList<Integer>();
 ArrayList<String> some = new ArrayList<String>();
 @SuppressWarnings("resource")
 Scanner sc = new Scanner(System.in);
 String input = sc.nextLine();
 for(int i = 0; i < input.length(); i++)
 {
 done.add(String.valueOf(input.charAt(i)));
 all.add(String.valueOf(input.charAt(i)));
 }
 int amount = done.size();
 for(int i = 0; i < amount; i++)
 {
 String letter = done.first();
 int tempNum = 0;
 for(int j = 0; j < all.size(); j++)
 {
 if(all.get(j).equals(letter))
 {
 tempNum++;
 }
 }
 num.add(tempNum);
 some.add(letter);
 done.remove(letter);
 }
 int highest = 0;
 int overallIndex = 0;
 for(int i = 0; i < num.size(); i++)
 {
 if(num.get(i) > highest)
 {
 highest = num.get(i);
 overallIndex = i;
 }
 }
 System.out.println("The most likely criminal is " + some.get(overallIndex) + " with " + highest + " witnesses.");
 }
}

Sample Input

aggdhaamfa

Sample Output

The most likely criminal is a with 4 witnesses.

• Sharon Ben Asher: You also need to know that it is very difficult to dry run and reverse engineer the logic of someone else's code. If you want our help then please enhance the problem description with sample input and output, logic description, edge cases, etc. Then, describe your solution and add description to the variables or better names
• h.j.k.: How long is 'too long'?
• Sean: @h.j.k. anything shorter or quicker to type is not "too long" i guess
• h.j.k.: Are you referring to the runtime performance of your 'simple code'? Did you only test with your sample input, or did you attempt to use a 1000-character String?
• Sean: @h.j.k with this code, runtime performance is not much of a problem for me; it can run in the background without needing to be touched; however, the time it takes to write is the issue; a quicker method of creating such program is my goal.

Answer 1

try-with-resources

Since Java 7, you can use try-with-resources on your Scanner for safe and efficient handling of the underlying I/O resource.

// Scanner scanner = new Scanner(System.in);
// ...
// scanner.close();
try (Scanner scanner = new Scanner(System.in)) {
 // ...
}

Interfaces over implementations, and generic type inference

Declarations should be done as List instead of ArrayList, and since Java 7, you are able to rely on generic type inference for simplification too:

// ArrayList<String> list = new ArrayList<String>();
List<String> list = new ArrayList<>();

Index-based retrieval across different List instances

Your usage of the num and some lists are merely the keys and values to what should be modeled as a Map, i.e. the number of occurrences to the 'smallest'

Problem formulation (and unit testing)

What will be the expected solution if there is an equal number of witnesses for two suspects? Or when there are no witnesses?

From your implementation, it suggests that it will pinpoint the 'smallest' character for the former, and will simply crash with an IndexOutOfBoundsException at some.get(overallIndex) for the latter, since some will be empty and overallIndex is initialized to 0.

This suggests that you should be writing a unit test for your implementation too (after putting the logic in its own method), to make sure your expectations are verified. On a related note, even your sample output is wrong, there's only 4 occurrences of a in aggdhaamfa.

Stream-based approach

Putting it altogether, the whole logic can be quite easily done in one return statement:

private static Map<Character, Integer> maxOccurrence(String input) {
 return Stream.of(Objects.toString(input, "").chars()
 .boxed()
 .collect(Collectors.groupingBy(
 i -> (char) i.intValue(),
 Collectors.counting()))
 .entrySet().stream()
 .collect(Collectors.groupingBy(
 Entry::getValue,
 TreeMap::new,
 Collectors.mapping(
 Entry::getKey,
 Collectors.reducing('~',
 (a, b) -> a.compareTo(b) < 0 ? a : b))))
 .lastEntry())
 .filter(Objects::nonNull)
 .collect(Collectors.toMap(
 Entry::getValue,
 entry -> entry.getKey().intValue()));
}

For starters, we deal with null input safely via Objects.toString(Object, String), before we stream on its characters via String.chars().

Then, the first Collectors.groupingBy(Function, Collector) gives us our preliminary result, counting() each character's presence.

Next, we need to then group by their occurrence, so the second Collectors.groupingBy(Function, Supplier, Collector) is used in conjunction with a TreeMap so that we can get our highest repeated character(s) as the lastEntry().

The character(s) are checked against each other using Collectors.reducing(T, BinaryOperator) to find out which is the 'smallest', using ~ as an initial value as it is an arbitrary large character compared to the standard English alphabet.

Finally, since lastEntry() can potentially give us a null for an empty Map, we wrap it up in a Stream just so we can filter null away, before finally converting the Entry representation into a Map via Collectors.toMap(Function, Function). This will return an empty Map at the very least.

Plain-old iteration

Of course, if the above approach looks too... advanced, the plain-old iteration approach is even simpler and easier to comprehend (with only a tiny bit of Java 8/9 magic):

private static Map<Character, Integer> maxOccurrence(String input) {
 Map<Character, Integer> occurrences = new HashMap<>();
 int maxCount = 0;
 char mostRepeated = '~';
 for (char c : Objects.toString(input, "").toCharArray()) {
 if (occurrences.merge(c, 1, Integer::sum) > maxCount
 && c < mostRepeated) {
 maxCount = occurrences.get(c);
 mostRepeated = c;
 }
 }
 return maxCount == 0
 ? Collections.emptyMap()
 : Map.of(mostRepeated, occurrences.get(mostRepeated));
}

Here, we update our occurrences map by Map.merge(K, V, BiFunction) and compare against maxCount/mostRepeated sequentially. The use of Collections.emptyMap() and Map.of(K, V) is slightly better too, as they ensure the results are immutable.

• Sean: I haven't really thought about using maps; thanks for suggesting it. I'll learn how to use those to make it similar. Thank you for the great insight.
• Sean: Quick question: is it unsafe to not use try-with-resources on a scanner, or is that just a sort of insurance policy?
• h.j.k.: Sort of an insurance policy. :) If you do use it, make sure the Scanner instance is only closed once in the main() method, when the program exits.
• Sean: I was told that the scanner instance did not need to be closed in most cases; should I still close it when I'm done with it?
• h.j.k.: Generally, it's a good practice that I/O resources be closed when you no longer require access to them, this helps the JVM and presumably the OS. Before Java 7, you might have come across older boilerplate code that does this explicitly, which has improved considerably since then. While there's nothing wrong with not closing a single Scanner instance inside the main() method since it will be closed when the method completes and the application ends, you should not rely on the same thinking once you start dealing with a multitude of opened files or network connections in a larger codebase.

Answer 2

for(int i = 0; i < input.length(); i++)
{
 done.add(String.valueOf(input.charAt(i)));
 all.add(String.valueOf(input.charAt(i)));
}

Instead of iterating over the input string like that, converting every single character to a new String, actually doing all of this twice, and adding each to a collection, you can convert the string to a list of Strings (for each character) like this:

List<String> inputChars = Arrays.asList(input.split(""));

Note that previously to Java 8 this results in the first element being an empty string, which must be handled accordingly.

Then add all of the characters in the array to the collections:

done.addAll(inputChars);
all.addAll(inputChars);

---

int highest = 0;
int overallIndex = 0;
for(int i = 0; i < num.size(); i++)
{
 if(num.get(i) > highest)
 {
 highest = num.get(i);
 overallIndex = i;
 }
}

To better structure your code, move the loop to a method findIndexOfHighest(). Your overallIndex actually is the indexOfHighest. Then you get the index of the highest element and the highest element like this:

int indexOfHighest = findIndexOfHighest();
int highest = num.get(indexOfHighest);

---

Add blank lines between blocks of code, e. g. between for loops. That makes your code much more readible.

---

int amount = done.size();
for(int i = 0; i < amount; i++)
{
 String letter = done.first();
 int tempNum = 0;
 for(int j = 0; j < all.size(); j++)
 {
 if(all.get(j).equals(letter))
 {
 tempNum++;
 }
 }
 num.add(tempNum);
 some.add(letter);
 done.remove(letter);
}

Here the inner loop can be a for-each loop. Also it should be in a separate method, because what it does is countOccurences(String s, char c). The variable tempNum should be called count or occurences.

• h.j.k.: List<String> inputChars = Arrays.asList(input.toCharArray()); does not compile.
• Sean: @D.Everhard while these tips are very helpful and good practice that I should learn, I found h.j.k's answers to be a little bit more useful.