Permutations or combinations of "strings" and more ...

Imagine you want to implement a password policy.
You want to make sure that a user does not use a permutation of his previous password (case sensitive).

The first trivial thing we notice is that
- If one password is a permutation of the other then they have the same length.

We try to implement an efficient solution using xor.
We use the fact that x ^ x == 0.

The complexity is O(n) to figure out if character array a is a permutation of character array b.

As a reminder:

O(1) < O(lg n) < O(n) < O(n lg n) < O(n^2) < O(2^n) < O(n!) 

If you would consider to sort the "string" and then to compare it then it would have
a complexitey of O(n log n) + O(n) = O((n log n) + n) = max(O(n log n) , O(n)) = O(n log n).
  

//returns 0 if a and b are permutations of each other, a value > 0 otherwise

int is_perm(char *a , char *b) {
    int la = 0 ;
    int lb = 0 ;
    int i = 0 ; 
    int check = 1 ;

    if(a == NULL || b == NULL)
        return(0) ;

    la = (int)strlen(a) ;
    lb = (int)strlen(b) ;

    if(la == 0 || lb == 0)
        return(0) ;

    if(la != lb)
        return(1) ;

    check = (a[0] ^ b[0]) ; 

    for(i = 1 ; i < la ; i++) {
        check = (check ^ (a[i] ^ b[i])) ;
    }
    
    return(check) ;
}

How does it work?
Let's try an example by hand:

Let a = "das" and b = "sad" and c = "des"

das = 00100110 10000110 11001110
sad = 11001110 10000110 00100110
des = 00100110 10100110 11001110

Let's call is_perm(a , b)

count = 'd' ^ 's' = 00100110 ^ 11001110 = 11101000
count = (count ^ ('a' ^ 'a')) = 11101000 ^ 00000000 = 11101000
count = (count ^ ('s' ^ 'd')) = 11101000 ^ (11001110 ^  00100110) = 00000000

count is 0, that means character array a is a permutation of character array b.

Let's call is_perm(a , c)


count = 'd' ^ 'd' = 00100110 ^ 00100110 = 00000000
count = (count ^ ('a' ^ 'e')) = 00000000 ^ (10000110 ^ 10100110) 
                                          =  00000000 ^ 00100000 = 00100000
count = (count ^ ('s' ^ 's')) = 00100000 ^ 00000000 = 00100000

count is 4, that means character array a is not a permutation of character array c.

Good luck in finding permutations.