CTCI Ch.1.2 Check Permutation

Question

Greetings and happy holidays,

My question involves problem "1.2 Check Permutation" from "Cracking The Coding Interview" 6th Ed.

When we compare the two strings, we check for any values in the array that are less than 0. This would indicate different char counts of our two strings. However, shouldn't the comparison be !== 0 instead of < 0? This would catch both over and undercounts of the chars. I didn't see this in the books Errata nor on any related search results.

Below is the provided code solution. (I mainly work in JS, so perhaps I'm reading the code incorrectly)

Many thanks in advance.

boolean permutation(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] letters = new int[128]; 

    char[] s_array = s.toCharArray();
    for (char c : s_array) {
            letters[c]++;
    }

    
    for (int i = 0; i < t.length(); i++) {
        int c = (int) t.charAt(i); 
        letters[c]--;
        if (letters[c] < 0) { // this is the line in question
            return false;
        }
    }
    return true;
}

Answer 1

The comparison for != 0 only makes sense after all the differences are computed. The way the code is structured allows an early detection.

The very first test is for s.length() != t.length(). Once the code passed it, we know that there are equal number of characters. It means that - if the strings are not permutations - there is a character which appears more in t than in s. As soon as such character is found, we conclude that t is not a permutation.