In this article, we will explore different approaches to check if two strings are permutations of each other in Java.
1. What Is a String Permutation?
A string permutation is a rearrangement of the characters of the string into a different sequence. Two strings are considered permutations of each other if they contain the same characters with the same frequencies, but possibly in a different order. For example, the strings “abc” and “bca” are permutations of each other.
2. Sorting
One way to check if two strings are permutations of each other is to sort both strings and compare them. If the sorted versions of both strings are equal, then the strings are permutations of each other.
import java.util.Arrays;
public class PermutationCheck {
public static boolean arePermutations(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
return Arrays.equals(charArray1, charArray2);
}
public static void main(String[] args) {
String str1 = "listen";
String str2 = "silent";
boolean result = arePermutations(str1, str2);
System.out.println("Are the two strings permutations of each other? " + result);
}
}
In the above code:
- We first check if the lengths of the two strings are equal. If not, they cannot be permutations.
- We convert both strings to character arrays and sort these arrays.
- We compare the sorted character arrays using
Arrays.equals. If they are equal, the strings are permutations of each other.
The code returns the following output:
Are the two strings permutations of each other? True
3. Count Frequencies
Another method to check for permutations is to count the frequency of each character in both strings and compare these counts.
import java.util.HashMap;
public class PermutationCheck {
public static boolean arePermutations(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
HashMap<Character, Integer> charCountMap = new HashMap<>();
for (char c : str1.toCharArray()) {
charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
}
for (char c : str2.toCharArray()) {
if (!charCountMap.containsKey(c)) {
return false;
}
charCountMap.put(c, charCountMap.get(c) - 1);
if (charCountMap.get(c) == 0) {
charCountMap.remove(c);
}
}
return charCountMap.isEmpty();
}
public static void main(String[] args) {
String str1 = "apple";
String str2 = "papel";
boolean result = arePermutations(str1, str2);
System.out.println("Are the two strings permutations of each other? " + result);
}
}In the above code:
- We check if the lengths of the two strings are equal.
- We create a HashMap to count the frequency of each character in the first string.
- We iterate over the second string, decrementing the count of each character in the HashMap.
- If a character is not found in the HashMap or its count goes to zero, we remove it from the map.
- If the HashMap is empty at the end, the strings are permutations of each other.
The code returns the following output:
Are the two strings permutations of each other? True
4. String That Contains a Permutation
To check if one string contains a permutation of another string, we can use a sliding window approach along with character frequency counting.
import java.util.HashMap;
public class PermutationCheck {
public static boolean containsPermutation(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
HashMap<Character, Integer> s1Count = new HashMap<>();
HashMap<Character, Integer> s2Count = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {
s1Count.put(s1.charAt(i), s1Count.getOrDefault(s1.charAt(i), 0) + 1);
s2Count.put(s2.charAt(i), s2Count.getOrDefault(s2.charAt(i), 0) + 1);
}
int matches = 0;
for (char c : s1Count.keySet()) {
if (s1Count.get(c).equals(s2Count.get(c))) {
matches++;
}
}
for (int i = 0; i < s2.length() - s1.length(); i++) {
if (matches == s1Count.size()) {
return true;
}
char start = s2.charAt(i);
char end = s2.charAt(i + s1.length());
if (s2Count.get(start).equals(s1Count.get(start))) {
matches--;
}
s2Count.put(start, s2Count.get(start) - 1);
if (s2Count.get(start).equals(s1Count.get(start))) {
matches++;
}
if (s2Count.containsKey(end)) {
if (s2Count.get(end).equals(s1Count.get(end))) {
matches--;
}
s2Count.put(end, s2Count.get(end) + 1);
if (s2Count.get(end).equals(s1Count.get(end))) {
matches++;
}
} else {
s2Count.put(end, 1);
}
}
return matches == s1Count.size();
}
public static void main(String[] args) {
String s1 = "ab";
String s2 = "eidbaooo";
boolean result = containsPermutation(s1, s2);
System.out.println("Does the second string contain a permutation of the first? " + result);
}
}In the above code:
- We first check if the length of the first string is greater than the second string. If so, it cannot contain a permutation.
- We use two HashMaps to count the frequencies of characters in the first string and in the current window of the second string.
- We slide the window over the second string, updating the counts and the number of matches between the two HashMaps.
- If the number of matches equals the size of the first string’s character count map, the second string contains a permutation of the first.
The code returns the following output:
Does the second string contain a permutation of the first? True
5. Summary
| Method | Advantages | Disadvantages |
|---|---|---|
| Sorting |
|
|
| Count Frequencies |
|
|
| String Contains a Permutation |
|
|
6. Conclusion
When determining if two strings are permutations of each other in Java, different methods offer various trade-offs in terms of efficiency, simplicity, and space complexity. Choosing the appropriate method depends on the specific requirements of the application:
- Sorting is suitable for scenarios where simplicity of implementation is prioritized and where string lengths are not excessively large.
- Count Frequencies is ideal for applications where efficiency for large strings is crucial and where additional space usage can be managed.
- String Contains a Permutation is beneficial for scenarios where checking substrings efficiently within large strings is required, despite the added complexity of implementation.
Overall, understanding these methods and their trade-offs allows developers to choose the most appropriate approach based on the specific constraints and requirements of their Java applications.
