Write a Java program to check if the two strings are anagrams.
Question Explanation
An anagram is a word or phrase formed by rearranging the letters of another, typically using all the original letters exactly once. The question of checking if two strings are anagrams is a common interview topic, particularly in software engineering. Interviewers often ask this to assess a candidate's understanding of string manipulation, data structures, and algorithmic thinking. This problem tests the candidate's ability to analyze the frequency of characters in both strings and compare them efficiently. Candidates might mistakenly think of sorting the strings as the only solution, which is not optimal in terms of performance. Instead, using a frequency counter or a hash map to count characters can yield a more efficient solution. This problem is relevant in various applications, including text processing, cryptography, and natural language processing. In real-world scenarios, understanding how to manipulate strings efficiently can lead to significant performance improvements, especially when dealing with large datasets. Thus, mastering this concept not only demonstrates technical skills but also shows an understanding of algorithm optimization. Key areas to focus on include: character frequency, hash maps, and time complexity analysis.
Sample Answers
Example 1: Using Character Frequency Count
To check if two strings are anagrams using a character frequency count, we can follow these steps:
- Normalize the strings: Convert both strings to the same case (e.g., lowercase) and remove any spaces.
- Check lengths: If the lengths of the two strings differ, return false immediately, as they cannot be anagrams.
- Count characters: Create an array of size 26 (for each letter of the alphabet) and iterate through the first string, incrementing the count for each character. For the second string, decrement the count.
- Final check: If all counts are zero, the strings are anagrams; otherwise, they are not.
Here’s the Java code implementing this approach:
public class AnagramChecker {
public static boolean areAnagrams(String str1, String str2) {
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
if (str1.length() != str2.length()) return false;
int[] charCount = new int[26];
for (char c : str1.toCharArray()) {
charCount[c - 'a']++;
}
for (char c : str2.toCharArray()) {
charCount[c - 'a']--;
}
for (int count : charCount) {
if (count != 0) return false;
}
return true;
}
}
This method runs in O(n) time, where n is the length of the strings, making it efficient.
Example 2: Sorting and Comparing
Another way to check if two strings are anagrams is to sort both strings and then compare them. Here’s how this method works:
- Normalize: Similar to the first example, convert both strings to lowercase and remove spaces.
- Sort the strings: Use a sorting algorithm to sort the characters of both strings.
- Compare: If the sorted versions of both strings are identical, then they are anagrams.
Here’s the Java implementation:
import java.util.Arrays;
public class AnagramChecker {
public static boolean areAnagrams(String str1, String str2) {
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
char[] str1Arr = str1.toCharArray();
char[] str2Arr = str2.toCharArray();
Arrays.sort(str1Arr);
Arrays.sort(str2Arr);
return Arrays.equals(str1Arr, str2Arr);
}
}
This method has a time complexity of O(n log n) due to the sorting step. While it's straightforward, it may not be as efficient as the frequency counting approach for larger strings.
Example 3: Using HashMap for Flexibility
A more flexible approach uses a HashMap to count character occurrences. This method allows for handling any character set, not just letters. Here’s how it works:
- Normalize: Convert both strings to lowercase and remove spaces.
- Create a HashMap: Use a HashMap to count character frequencies from the first string.
- Decrement counts: For each character in the second string, decrement the corresponding count in the HashMap.
- Final check: If any count is non-zero at the end, the strings are not anagrams.
Here’s the Java implementation:
import java.util.HashMap;
public class AnagramChecker {
public static boolean areAnagrams(String str1, String str2) {
str1 = str1.replaceAll("\\s+", "").toLowerCase();
str2 = str2.replaceAll("\\s+", "").toLowerCase();
if (str1.length() != str2.length()) return false;
HashMap<Character, Integer> charCount = new HashMap<>();
for (char c : str1.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
for (char c : str2.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) - 1);
}
for (int count : charCount.values()) {
if (count != 0) return false;
}
return true;
}
}
This method runs in O(n) time and is useful when working with diverse character sets.
Keywords
Ready to practice more questions?
Explore our collection of technical interview questions from top companies.
View All Questions