Hash Tables II: Advanced Applications

How Hash Tables Solve String Problems

Hash tables are particularly effective for string operations because they provide:

• O(1) lookups - Quickly check if a character exists or its frequency
• Efficient counting - Track occurrences of characters without multiple scans
• Flexible key-value pairing - Store characters as keys with various metadata as values

Implementation Steps

1. 1

   Create Frequency Map

   Initialize a hash map to store character frequencies

   Map frequencyMap = new HashMap<>();

   This map will associate each character with the number of times it appears in the string.

2. 2

   Count Character Frequencies

   Iterate through the string to count occurrences

   for (char c : str.toCharArray()) { frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1); }

   The getOrDefault method returns the current frequency if the character exists, or 0 if it's not yet in the map.

3. 3

   Find First Non-Repeating

   Search for the first character with frequency 1

   for (char c : str.toCharArray()) { if (frequencyMap.get(c) == 1) { return c; } } return '_'; // Return a placeholder if no non-repeating character is found

   We scan the string again in the original order to find the first character with a frequency of 1.

Complete Implementation

public char findFirstNonRepeating(String str) {
    // Edge case: empty string
    if (str == null || str.isEmpty()) {
        return '_';
    }
    
    // Create frequency map
    Map frequencyMap = new HashMap<>();
    
    // Count character frequencies
    for (char c : str.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }
    
    // Find first non-repeating character
    for (char c : str.toCharArray()) {
        if (frequencyMap.get(c) == 1) {
            return c;
        }
    }
    
    // No non-repeating character found
    return '_';
}

Visual Example

Let's trace the algorithm with the input string "leetcode":

Step 1: Build Frequency Map

Step 2: Scan the String in Original Order

Character	Frequency	Is First Non-Repeating?
'l'	1	Yes ✓
Check stopped after finding the answer

Result: 'l'

Alternative Approaches and Optimizations

Using LinkedHashMap to Maintain Order

If we want to avoid a second pass through the string, we can use a LinkedHashMap, which maintains insertion order:

public char findFirstNonRepeatingOptimized(String str) {
    Map frequencyMap = new LinkedHashMap<>();
    
    // Count frequencies
    for (char c : str.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }
    
    // Check the map in insertion order
    for (Map.Entry entry : frequencyMap.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }
    
    return '_';
}

Note: This approach is not correct for our specific problem, as it would check characters in order of first appearance rather than original string order.

Using a Single-Pass Approach with Index Tracking

For large strings, we can optimize by tracking the index of each character's first appearance:

public char findFirstNonRepeatingIndexTracking(String str) {
    Map indexMap = new HashMap<>();
    Map repeatingMap = new HashMap<>();
    
    // Track first index and whether character repeats
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (!repeatingMap.containsKey(c)) {
            // First occurrence
            indexMap.put(c, i);
            repeatingMap.put(c, false);
        } else {
            // Repeated occurrence
            repeatingMap.put(c, true);
        }
    }
    
    // Find character with earliest index that doesn't repeat
    int minIndex = Integer.MAX_VALUE;
    char result = '_';
    
    for (Map.Entry entry : repeatingMap.entrySet()) {
        if (!entry.getValue()) {
            char c = entry.getKey();
            int index = indexMap.get(c);
            if (index < minIndex) {
                minIndex = index;
                result = c;
            }
        }
    }
    
    return result;
}

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the string
  • We scan the string twice, but multiple O(n) operations still result in O(n)
• Space Complexity: O(k), where k is the number of unique characters
  • In practice, this is usually O(1) for most strings (limited character set)
  • At most O(26) for lowercase English letters, O(52) including uppercase

Exercise 1: First Non-Repeating Character

Implement a method to find the first non-repeating character in a string.

public char findFirstNonRepeating(String str) {
    // Your implementation here
    // Return the first non-repeating character
    // Return '_' if no such character exists
}

Exercise 2: Character Frequency Analysis

Implement a method to find the most frequent character in a string.

public char findMostFrequent(String str) {
    // Your implementation here
    // Return the most frequent character
}

// Hints:
// 1. Use a HashMap to count character frequencies
// 2. Track the maximum frequency and corresponding character
// 3. Return the character with highest frequency

Exercise 3: Anagram Detection

Implement a method to determine if two strings are anagrams using a hash table.

public boolean areAnagrams(String s1, String s2) {
    // Your implementation here
    // Return true if strings are anagrams
    
    // Hints:
    // 1. Compare string lengths first (quick check)
    // 2. Count frequencies of characters in both strings
    // 3. Compare the frequency maps
}

Exercise 4: Valid Palindrome Permutation

Implement a method to check if a string can be rearranged to form a palindrome.

public boolean canFormPalindrome(String str) {
    // Your implementation here
    // Return true if the string can be rearranged to form a palindrome
    
    // Hint: A string can form a palindrome if at most one character
    // appears an odd number of times
}

Exercise 5: First Unique Substring

Find the first unique substring of length k in a string.

public String firstUniqueSubstring(String str, int k) {
    // Your implementation here
    // Return the first substring of length k that appears only once
    // Return an empty string if no such substring exists
    
    // Hint: Use a hash map to track frequencies of substrings
}

Exercise 6: Advanced - Two Sum Problem

Given an array of integers and a target sum, find two numbers that add up to the target.

public int[] twoSum(int[] nums, int target) {
    // Your implementation here
    // Return indices of the two numbers that add up to target
    
    // Hint: Use a hash map to track values you've seen so far
    // If target - current number exists in map, you found the pair
}