Checking for weak string isomorphism in Java

Question

Intro

I call two \$n\$-strings \$s\$ and \$z\$ over the alphabet \$\Sigma\$ weakly isomorphic if their character frequency multisets are equal. In other words, for an input strings \$s\$, we derive a function \$f_s\colon\Sigma \rightarrow \mathbb{N}\$ such that for any character of \$c \in s\$, the value \$f_s(c)\$ is the number of times \$c\$ appeared in \$s\$. Finally we take the multiset of the range \$\mathcal{R}(f_s)\$ of \$f_s\$. We, then, derive the \$\mathcal{R}(f_z)\$ and return true if and only if \$\mathcal{R}(f_s) = \mathcal{R}(f_z)\$.

Code

public static boolean areWeaklyIsomorphic(String s, String z) {

    Objects.requireNonNull(s, "The first input string is null");
    Objects.requireNonNull(z, "The second input string is null");

    if (s.length() != z.length()) {
        return false;
    }

    Map<Character, Integer> counterMapS = new HashMap<>();
    Map<Character, Integer> counterMapZ = new HashMap<>();

    for (char ch : s.toCharArray()) {
        counterMapS.put(ch, counterMapS.getOrDefault(ch, 0) + 1);
    }

    for (char ch : z.toCharArray()) {
        counterMapZ.put(ch, counterMapZ.getOrDefault(ch, 0) + 1);
    }

    if (counterMapS.size() != counterMapZ.size()) {
        return false;
    }

    List<Integer> counterListS = new ArrayList<>(counterMapS.values());
    List<Integer> counterListZ = new ArrayList<>(counterMapZ.values());

    counterListS.sort(Integer::compare);
    counterListZ.sort(Integer::compare);

    return counterListS.equals(counterListZ);
}

Answer 1

By defining a custom data structure to map primitive types char to int...

public class AssociativeArray {
    
    public static CharToIntArray charToPositiveInt() {
        return new CharToIntArray(-1);
    }
    
    public static class CharToIntArray extends AssociativeArray {
        
        private int undefined;
        private char[] keys;
        private int[] values;
        
        {
            this.keys = new char[] {  };
            this.values = new int[] {  };
        }
        
        public CharToIntArray(int undefined) {
            this.undefined = undefined;
        }
        
        public int get(char key) {
            int value = this.undefined;
            for ( int i = 0; i < this.keys.length; i++ ) {
                if ( key == this.keys[i] ) {
                    value = this.values[i];
                    break;
                }
            }
            
            return value;
        }
        
        public int put(char key, int value) {
            int returnee = this.undefined;
            int indexOf = this.undefined;
            
            for ( int i = 0; i < this.keys.length; i++) {
                if ( key == this.keys[i] ) {
                    indexOf = i;
                    break;
                }
            }
            
            if ( indexOf == this.undefined) {
                int nextLength = this.keys.length + 1;
                char[] nextKeys = new char[nextLength];
                int[] nextValues = new int[nextLength];
                
                for ( int i = 0; i < this.keys.length; i++ ) {
                    nextKeys[i] = this.keys[i];
                    nextValues[i] = this.values[i];
                }
                
                synchronized(this.keys) {
                    this.keys = nextKeys;
                    this.values = nextValues;
                }
                
                indexOf = nextLength - 1;
            } else {
                returnee = this.values[indexOf];
            }
            
            this.keys[indexOf] = key;
            this.values[indexOf] = value;
            
            return returnee;
        }
        
        public int getOrDefault(char key, int value) {
            int returnee = this.get(key);
            
            if ( returnee == this.undefined ) {
                
                returnee = value;
                this.put(key, value);
            }
            
            
            return returnee;
        }
        
        public int size() {
            return this.keys.length;
        }
        
        public int[] values() {
            int[] returnee = new int[this.keys.length];
            for ( int i = 0; i < returnee.length; i++ ) {
                returnee[i] = this.values[i];
            }
            return returnee;
        }
        
        public char[] keys() {
            char[] returnee = new char[this.keys.length];
            for ( int i = 0; i < returnee.length; i++ ) {
                returnee[i] = this.keys[i];
            }
            return returnee;
        }
    }
}

... there is a 50% efficiency improvement of the implementation ...

public static boolean areWeaklyIsomorphicPrimitives(String s, String z) { 
        
    Objects.requireNonNull(s, "The first input string is null");
    Objects.requireNonNull(z, "The second input string is null");

    if (s.length() != z.length()) {
        return false;
    }

    CharToIntArray counterMapS = AssociativeArray. charToPositiveInt();
    CharToIntArray counterMapZ = AssociativeArray. charToPositiveInt();

    for (char ch : s.toCharArray()) {
        counterMapS.put(ch, counterMapS.getOrDefault(ch, 0) + 1);
    }

    for (char ch : z.toCharArray()) {
        counterMapZ.put(ch, counterMapZ.getOrDefault(ch, 0) + 1);
    }

    if (counterMapS.size() != counterMapZ.size()) {
        return false;
    }

    int[] sCounters =  counterMapS.values();
    int[] zCounters = counterMapZ.values();

    Arrays.sort(sCounters);
    Arrays.sort(zCounters);

    return Arrays.equals(sCounters, zCounters);
}

... all that preserving the complexity of the implementation, therefore improvements are possible without changing the algorithm.

Answer 2

It could be improved by using primitives (char, int) alternatively to their Object version (Character, Integer) to the expense of losing the low complexity in terms of readability since using primitives requires developing dedicated data structures or working with array of arrays of primitives and along with proofing isomorphism implement the characters look up into the arrays.