Frequencies of Characters By Brute Force Vs Hashing

Java · DSA · Character Hashing

Character frequencies — hashing vs brute force

Same problem, two solutions, wildly different scaling. Type a string below and watch both approaches work in real time.

🔤 The 26-bucket hasher

Every lowercase letter maps straight to hash[ch - 'a'] — no scanning required.

String input

Query characters

01 The two implementations

Both take a string and answer "how many times does character X appear?" — but they get there very differently.

import java.util.Scanner;
public class CharacterFrequenciesByHashing {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] arr = new char[n];
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.next().charAt(0);
            hash[arr[i] - 'a']++;
        }
        int q = sc.nextInt();
        while (q != 0) {
            char ch = sc.next().charAt(0);
            if (ch >= 'a' && ch <= 'z') {
                System.out.print(ch + "=" + hash[ch - 'a'] + " ");
            } else {
                System.out.print(ch + "=" + 0 + " ");
            }
            q--;
        }
    }
}

import java.util.Scanner;
public class CharacterHashingByBruteForce {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] arr = new char[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.next().charAt(0);
        }
        int q = sc.nextInt();
        while (q > 0) {
            char ch = sc.next().charAt(0);
            findFrequencies(arr, ch);
            q--;
        }
    }
    private static void findFrequencies(char[] arr, char ch) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == ch) count++;
        }
        System.out.print(ch + "=" + count + " ");
    }
}

02 Watch the gap explode

Drag the sliders — hashing does n + q work total. Brute force does n × q.

⚡ Operation count race

n = string length, q = number of queries

n (string length): 1,000

q (queries): 1,000

2,000 ops

Hashing (n + q)

1,000,000 ops

Brute force (n × q)

✕ Brute force is doing 500× more work at these values.

Metric	Hashing	Brute Force
Preprocessing	O(n)	O(n)
Per query	O(1)	O(n)
Total (n, q queries)	O(n + q)	O(n × q)
Extra space	O(26) → O(1)	O(1)

03 Deep dive: what's actually happening

Why hashing is O(1) per query

The moment you compute hash[ch - 'a'], you're not searching — you're addressing. 'a' maps to index 0, 'z' to index 25, always. There's no comparison loop; the array index calculation itself IS the lookup. This is why it's called direct-address hashing rather than a general hash table — the "hash function" (ch - 'a') is a perfect, collision-free mapping onto a small, known range.

Why brute force is O(n) per query

findFrequencies has no memory of previous work. Ask it about 'r' twice in a row and it re-scans the entire array both times. It treats every query as if it's the first and only question ever asked — there's no state carried between calls.

The core lesson: hashing pays a fixed O(n) cost once, then answers every future question for free. Brute force pays a variable cost every single time. The break-even point is roughly q = 1 — even a single query benefits from having precomputed the counts, and the gap only widens from there.

The dead-array subtlety

In the hashing version, arr[] is filled but never read again after the counting loop. It's only needed if a later part of the program needs the original sequence — for pure frequency counting, you could drop it and keep just hash[26]. In brute force, arr[] is essential since every query re-reads it.

Interview tip: if you notice you're hashing and storing the raw array but never using the raw array again, that's often a sign you can slim your solution down — one less array to allocate.

The bounds-checking bug (and why it mattered)

The original hashing version had no guard on ch - 'a'. Feed it an uppercase letter or digit and you get a negative or oversized index → ArrayIndexOutOfBoundsException. Brute force never had this problem because it never uses the character as an index — it only ever compares it with ==. That's a structural safety difference, not a coincidence: any time you convert an input into an array index, you own the responsibility of validating that input first.

04 Quick revision — key points

1

Hashing = O(1) lookup

Direct-address hashing turns a character into an array index. No loop, no comparison — just arithmetic.

2

Brute force = O(n) lookup

Every query re-scans the whole array. No memory of past work is kept.

3

Total cost formula

Hashing: O(n + q). Brute force: O(n × q). The multiplication is what kills brute force at scale.

4

Always validate before indexing

ch - 'a' is only safe for 'a'–'z'. Guard the range before using a value as an array index.

5

26 is a magic number here

The hash array is sized 26 because the alphabet is fixed and small — a big reason character hashing is so clean compared to integer hashing.

6

Preprocess once, query forever

This is the general hashing principle, not just a character-counting trick — pay the setup cost once, then answer in O(1).

Situation	Prefer
Many queries expected (q large)	Hashing
One-off, single query, tiny n	Either — brute force is simpler to write
Fixed, small alphabet (a–z, ASCII)	Hashing (array-based, no HashMap needed)
Unbounded/unknown character set	HashMap-based hashing instead of a fixed array

Reference notes on character-frequency hashing vs brute force for Java-based DSA practice.