Check Permutation

If I ask you to do a method to find out if two strings are permutations of each other, how would you do it?

Think about what it means for a String to be a permutation of the other? For example “ABC” is a permutation of “CBA”, but “XBA” is not - since you cannot change the letters of “ABC” to obtain “XBA”.

👉 Link here to the repo where you can solve the problem

👌 Tips

There is a solution that is in O(N Log N) and there is another one which is in O(N)

Two permutations have the same length but in different order, would it make a difference to order them?

Have you thought about using a HashTable?

👊 Solution 1

If we can order both Strings and then compare them. This would take an estimated time of O(N Log N + M Log M), which is the time required to order both Strings.

It is worth taking into account that although this algorithm is not the most efficient, it may be more preferable in another way. Since it is very clean, simple and easy to understand.

public boolean sortingSolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;
    String s1Sorted = sortString(s1); // O(s1 log s1)
    String s2Sorted = sortString(s2); // O(s2 log s2)
    return s1Sorted.equals(s2Sorted);
}

static String sortString(String string) {
    char temp[] = string.toCharArray();
    Arrays.sort(temp);
    return new String(temp);
}

👊 Solution 2

With a HashMap we could obtain a solution that is more efficient - O(N), where N is the length of one of the Strings.

This solution is a bit more complicated to understand and much more verbose. What we do is iterate over both Strings once (since we know they have the same length) and for the first String we add a +1 in that character, and for the second string we make a -1. In the end we add all the remaining values ​​and any number other than 0 we will know that they have different character accounts.

public boolean hashMapSolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;

    char[] s1Chars = s1.toCharArray();
    char[] s2Chars = s2.toCharArray();
    Map<Character, Integer> checker = new HashMap<>();

    for (int I = 0; I < s1L; I++) {
        char c1 = s1Chars[I];
        char c2 = s2Chars[I];
        insertCharToHashMap(checker, c1, 1);
        insertCharToHashMap(checker, c2, -1);
    }

    int sum = checker.values().stream().reduce(0, Integer::sum);
    return sum == 0;
}

void insertCharToHashMap(Map<Character, Integer> hashMap, char c, int value) {
    if (hashMap.containsKey(c)) {
        int newVal = hashMap.get(c) + value;
        hashMap.put(c, newVal);
    } else {
        hashMap.put(c, value);
    }
}

👊 Solution 3

With an Array and assuming our solution is within the ASCII dictionary we could have another solution that is written more simply and cleanly and in O(N).

We use an Array with 128 spaces. We go over String 1 first by adding +1 for each character we find in the correct Array space. Then we iterate on String 2 and if any character reduces below 0 it means that there are different characters in the Second String, it is not a permutation.

public boolean arraySolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;
    int[] checker = new int[128];

    char[] s1Chars = s1.toCharArray();
    char[] s2Chars = s2.toCharArray();
    // we know that ASCII chars are from 0 to 127
    for (char s1Char : s1Chars) {
        checker[s1Char]++;
    }

    for (char s2Char : s2Chars) {
        checker[s2Char]—;
        if (checker[s2Char] < 0) return false;
    }
    return true;
}

Always remember to ask if you are only using the ASCII set characters

---

Borrowed question from the book "Cracking the coding interview"