Frequency Of Characters In A String In Java Leetcode Solution

Understanding the frequency of characters within a string is a fundamental skill in programming, often encountered in technical interviews and competitive programming challenges like those on LeetCode. Character frequency analysis forms the basis for solving a variety of problems, from checking for anagrams to data compression.

In this article, you will learn how to efficiently calculate the frequency of each character in a given string using different approaches in Java.

Problem Statement

The core problem is to count the occurrences of each unique character within a given input string. For example, if the string is "hello", we need to determine that 'h' appears once, 'e' once, 'l' twice, and 'o' once. This seemingly simple task has significant implications for algorithms that rely on character distribution, such as finding the most frequent character, determining if a string is an anagram of another, or building frequency maps for Huffman coding.

Example

Let's consider the input string: "programming"

The expected output showing character frequencies would be:

• p: 1
• r: 2
• o: 1
• g: 2
• a: 1
• m: 2
• i: 1
• n: 1

Background & Knowledge Prerequisites

To effectively understand the solutions presented, readers should have a basic grasp of the following Java concepts:

• Strings: Immutability, charAt() method, length().
• Loops: for loops for iterating over strings.
• Data Structures:
• Arrays: Basic declaration and access.
• Maps (HashMap): Storing key-value pairs, put(), get(), containsKey(), getOrDefault().
• Primitive Types: char and int.

No special imports or complex setup are required beyond the standard Java Development Kit (JDK).

Use Cases or Case Studies

Character frequency analysis is a versatile tool with numerous applications:

• Anagram Detection: Two strings are anagrams if they have the same characters with the same frequencies (e.g., "listen" and "silent").
• Unique Character Check: Determining if a string contains all unique characters (e.g., no repeated characters).
• Most/Least Frequent Character: Finding the character that appears the most or least often in a text.
• Data Compression (e.g., Huffman Coding): Frequencies are used to assign shorter codes to more common characters.
• Palindrome Permutation: Checking if a string can be rearranged to form a palindrome (requires character counts to have at most one character with an odd frequency).

Solution Approaches

We will explore two common and efficient approaches to solve this problem: using a HashMap and using an array.

Approach 1: Using a HashMap

This approach uses a HashMap to store character-count pairs. It is highly flexible as it can handle any character set (ASCII, Unicode) without needing to pre-allocate a large fixed-size array.

• Summary: Iterate through the string, and for each character, increment its count in the HashMap. If the character is encountered for the first time, initialize its count to 1.

// CharacterFrequencyHashMap
import java.util.HashMap;
import java.util.Map;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        String str = "programming";
        Map<Character, Integer> charFrequencies = new HashMap<>();

        // Step 1: Iterate through each character of the string
        for (char c : str.toCharArray()) {
            // Step 2: Use getOrDefault to safely increment count
            // If character 'c' is already in the map, get its count and add 1.
            // If not, get 0 (default value) and add 1, then put it into the map.
            charFrequencies.put(c, charFrequencies.getOrDefault(c, 0) + 1);
        }

        // Step 3: Print the character frequencies
        System.out.println("Character frequencies (HashMap):");
        for (Map.Entry<Character, Integer> entry : charFrequencies.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Run

Sample Output:

Character frequencies (HashMap):
p: 1
r: 2
a: 1
g: 2
i: 1
m: 2
n: 1
o: 1

Stepwise Explanation:

1. Initialize HashMap: A HashMap named charFrequencies is created to store characters as keys and their frequencies as values.
2. Iterate String: The input string str is converted into a character array using toCharArray(), allowing for easy iteration through each character.
3. Update Frequencies: For each character c:

• charFrequencies.getOrDefault(c, 0) retrieves the current count of c from the map. If c is not yet in the map, it returns 0.
• + 1 increments this count.
• charFrequencies.put(c, ...) updates the map with the new count for c.

1. Print Results: The code then iterates through the entrySet() of the HashMap to print each character and its corresponding frequency.

Approach 2: Using an Array

This approach is suitable when dealing with a known, limited character set, such as ASCII (256 characters) or lowercase English letters (26 characters). It leverages the fact that char values can be implicitly cast to int and used as array indices.

• Summary: Create an integer array (e.g., int[256]). Iterate through the string, and use each character's ASCII value as an index to increment the count in the array.

// CharacterFrequencyArray
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        String str = "programming";
        // Assuming ASCII characters (0-255).
        // For only lowercase English letters, a smaller array of size 26 could be used:
        // int[] charFrequencies = new int[26]; and index would be c - 'a';
        int[] charFrequencies = new int[256];

        // Step 1: Iterate through each character of the string
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // Step 2: Use the character's ASCII value as an index to increment its count
            charFrequencies[c]++;
        }

        // Step 3: Print the character frequencies
        System.out.println("Character frequencies (Array):");
        for (int i = 0; i < charFrequencies.length; i++) {
            if (charFrequencies[i] > 0) {
                // Cast the index back to char to print the character
                System.out.println((char) i + ": " + charFrequencies[i]);
            }
        }
    }
}

Run

Sample Output:

Character frequencies (Array):
a: 1
g: 2
i: 1
m: 2
n: 1
o: 1
p: 1
r: 2

Stepwise Explanation:

1. Initialize Array: An int array charFrequencies of size 256 (to cover all standard ASCII characters) is created. All elements are initialized to 0 by default.
2. Iterate String: The code iterates through the string using a traditional for loop and str.charAt(i) to get each character.
3. Increment Count: For each character c, its ASCII value is implicitly used as an index into the charFrequencies array, and the value at that index is incremented (charFrequencies[c]++).
4. Print Results: The code then iterates through the charFrequencies array. If an element charFrequencies[i] is greater than 0, it means the character corresponding to index i appeared in the string. The index i is cast back to char ((char) i) for printing.

Conclusion

Counting character frequencies in a string is a foundational programming task with multiple practical applications. Both the HashMap and array approaches offer efficient ways to achieve this, each with its own advantages. The HashMap provides flexibility for any character set, while the array approach offers superior performance and simplicity when dealing with limited character ranges like ASCII. Choosing the right approach depends on the specific constraints of the problem, particularly the expected character set.

Summary

• Problem: Count occurrences of each unique character in a string.
• HashMap Approach:
• Mechanism: Uses HashMap to store counts.
• Pros: Handles any character set (ASCII, Unicode) gracefully; memory usage adapts to unique characters.
• Cons: Slightly slower than arrays due to object overhead and hashing.
• Array Approach:
• Mechanism: Uses int[] where index corresponds to character's ASCII value.
• Pros: Extremely fast (O(1) access); simple to implement for fixed character sets.
• Cons: Requires pre-allocating memory for the entire possible character range, even if many characters are not present (e.g., int[65536] for full Unicode could be large).
• Application: Crucial for problems like anagrams, palindromes, and basic text analysis.