Learn

Your counts match on every test until one of them reaches 128

26 October 2026 · One mistake, one counterexample

Counting problems feel safe. You build two frequency maps, compare them, and every sample passes. Then the interviewer asks what happens when a character appears a few hundred times, and the comparison you wrote without thinking turns out to depend on how big the number is.

The situation

You are asked whether two strings use exactly the same characters the same number of times. The natural Java answer counts both into a Map<Character, Integer> and compares the counts:

static boolean sameCounts(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Integer> a = new HashMap<>(), b = new HashMap<>();
    for (char c : s.toCharArray()) a.merge(c, 1, Integer::sum);
    for (char c : t.toCharArray()) b.merge(c, 1, Integer::sum);
    for (char c : a.keySet()) {
        if (a.get(c) != b.get(c)) return false;
    }
    return true;
}

On "listen" and "silent" it returns true. On "ab" and "aa" it returns false. Both right, and most hand-made tests stop there.

The input that breaks it

Pass the same string twice: 128 copies of the letter a. The answer must be true. The method returns false.

With 127 copies it returns true. Nothing about the algorithm changed between the two inputs; only the size of one count did.

The reason is that a.get(c) returns an Integer, an object, and != between two objects compares references, not values. Java keeps a cache of Integer objects for small values, -128 to 127 by default, so boxing 5 twice hands you the same object and the reference check happens to agree with the value check. Boxing 128 twice gives two different objects with equal values, and != says they differ.

The hidden assumption is == on numbers compares numbers. It holds for int. It does not hold for Integer, and a map, a list or a generic method always hands you Integer. Small tests hide it because almost every count in a hand-written example is below 128.

Python has a quieter version of the same trap. is compares identity, and CPython happens to reuse objects for small integers, so x is y can be true for 256 and false for 300 with equal values. Recent Python versions warn when you write is against a number literal, but not when both sides are variables.

The fix and the invariant

Compare values, not objects:

if (!a.get(c).equals(b.get(c))) return false;

Objects.equals(a.get(c), b.get(c)) also works and is safe when either side is null. Note what null means here: a character in s that never appears in t. With .equals called on the count from a, which is never null, the missing case returns false as it should. Unboxing both sides into int would throw a NullPointerException there instead.

The invariant to say: in Java, == on anything that came out of a collection compares references; numbers from collections are compared with equals, or unboxed on purpose after a null check.

In Python, compare numbers with ==, always, and keep is for None.

What to say out loud

When you write the comparison: "These counts come out of a map, so they are Integer objects. I'm comparing them with equals, because != would compare references and only agrees with the values below 128." It takes five seconds, and it tells the interviewer you know where your types change under you.

If you have already written !=, catch it on your own trace: "Wait, these are boxed. That check is a reference comparison; let me use equals." Then name the input that would have exposed it: one character repeated 128 times. Saying the breaking input shows you understand the bug, not just the fix.

The exercise

1. Find the last three Java solutions you wrote that store numbers in a Map, a List or an array of Integer.
2. Search each one for == and !=, and mark every comparison where both sides are Integer rather than int.
3. For each mark, write the smallest input that pushes a value to 128 or below -128, and predict the wrong answer before running it.
4. Replace each comparison with equals or Objects.equals, then decide out loud what happens when one side is null.
5. If you also practise in Python, search the same solutions for is and remove every use that is not is None.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question rather than revealing the solution, so "what type does get return, and what does != compare for that type?" is the kind of question it would put to you. Saying "I'm stuck" gives one more step, up to pseudocode, never finished code.