javastringalgorithmanagram

Check if two Strings are Anagrams Without using built-in features that require Import

I need to compare 2 strings and see if the number of every character each of them contain is the same.

Requirement:

Without using any packages or imports

My idea:

I want to check if a char from charsA exists within charsB. And if it does, I'll remove it from charsB.

And if the length of charsB is 0 by the end of the for loop, then I know it is an anagram

Issue:

It might end up deleting each character that matches a particular character more than once.

For example, if input is "oellh" and "heloo" (result should be false):

My code:

static boolean isAnagram(String a, String b) {
    boolean isAnagram;
    
    //case 2:
    //if strings lengths dont match isAnagram is set to false
    if(a.length() != b.length()){isAnagram = false;}
    
    // will turn each string into an array or characters
    String[] charsA = a.split("");
    String[] charsB = b.split("");
   
    for (int i = 0; i < a.length(); i++) {
        // some code to compare the strings here.
    }
    
    return isAnagram;
}

Test cases

*Input:

"hello", "olhel"   // case one
"helloq", "olhel"  // case two
"helloq", "olheln" // case three

Output:

true              // case one
false             // case two
false             // case three
Solution

  • Generate a HashMap of frequencies of symbols for both given strings.

    Then compare the two maps. If they are equal, then the strings are anagrams.

    public static boolean isAnagram(String a, String b) {
    return getFrequencies(a).equals(getFrequencies(b));
}

public static Map<Integer, Long> getFrequencies(String str) {
    
    return str.codePoints()
        .boxed()
        .collect(Collectors.groupingBy(
            Function.identity(),
            Collectors.counting()
        ));
}

    main()

    public static void main(String[] args) {
    System.out.println(isAnagram("hello", "olhel"));
    System.out.println(isAnagram("hello", "olhelq"));
}

    Output:

    true
false

    Without using any packages or imports

    There are different possibilities, the optimal choice would depend on the constraints on the strings received as an input.

    If we expect that input will contain only letters of the English alphabet, then we could handle this case by populating two arrays of length 26 where each element corresponds to a frequency of a particular letter (as shown in the link provided by @Federico klez Culloca in the comments). To get the result, we can compare these arrays iterating over the indices and checking values at the same index are equal. This algorithm will run in a linear time O(n) (as well as map-based solution shown above).

    In case if we can't expect that symbols in the given strings would be in a particular range, then we can extract arrays of characters from both strings, sort them and compare both array character by character. This algorithm will run in a linear-logarithmic time O(n * log n) because it requires sorting. And since we are not allowed to use imports (like Arrays utility class) then we need to implement a linear-logarithmic sorting algorithm (like quicksort or merge-sort) manually.