Two ways to determine if one string is a permutation of another

Given two strings, write a function to determine if one is a permutation of the other.

/**
 * Determines if s1 is a permutation of s2
 * @param {string} s1
 *  @param {string} s2
 * @returns {boolean}
 */
function isPermutation(s1, s2) {
    // Fill in your solution here
}

Note,

The function is case-sensitive. i.e. “a” is not the same as “A”.
Whitespace counts. i.e. “ab c d” is not the same as “abcd”.

TL;DR:

Sorting and Comparing
Use a Frequency Counter

What is a permutation?

A permutation is an arrangement or rearrangement of the elements of a set into a particular order. The elements of a string are its characters. So a string is a permutation of another if it satisfies the following conditions,

Both have the same characters.
Both have the same length.

Like “AB C” and “B CA”.

Examples:

Input: “hxrxqdhxttoi gocstmubnahffvmwpfsd BJUIK 345 >><<” and “xhrx qdhxtotigocstmubhnaffvmw fpdsKUIJB 453 <<>>”
Output: true

Input: “aaaaa45367%%^” and “^^^&&&%%aaaa”
Output: false

1. Sorting and Comparing

Sort the two strings.
Compare the two sorted strings. If they are equal, then the strings are permutations of each other.

/**
 * Determines if s1 is a permutation of s2 by 
 * sorting the two strings and comparing
 * @param {string} s1
 * @param {string} s2
 * @returns {boolean}
 */
function isPermutation(s1, s2) {
    if (s1.length !== s2.length) {
        return false // Early return if lengths don't match
    }

    // Convert to an array and sort
    s1 = Array.from(s1).sort().join('')
    s2 = Array.from(s2).sort().join('')

    return (s1 === s2)
}

Time complexity	O(n log n)
Space complexity	O(n). The size of the array grows linearly with the input string length.

== vs === in JavaScript

Both == and === operators check whether its two operands are equal and return a Boolean result. However, if the operands are of different types, the equality operator (==) attempts to convert them to a common type before comparison. The strict equality operator (===) always considers operands of different types to be different.

"1" == 1 // true
"1" === 1 // false

cracking the coding interview — Don’t miss out on the book everyone is talking about.
Grab your copy before it’s gone!

2. Use a Frequency Counter

Create an object to hold counts of each character.
For each character in s1, increment the character’s frequency. For each character in s2, decrement frequency.
In the end, if all the values in the object are zeros, then the strings are permutations of each other.

/**
 * Determines if s1 is a permutation of s2 by 
 * checking character counts
 * @param {string} s1
 * @param {string} s2
 * @returns {boolean}
 */
function isPermutation(s1, s2) {
    if (s1.length !== s2.length) {
        // Early return if lengths don't match
        return false 
    }

    const counter = {}

    for (let i = 0; i < s1.length; i++) {
        if (!counter[s1[i]]) {
            counter[s1[i]] = 0
        }
        ++counter[s1[i]] // Increment count for s1

        if (!counter[s2[i]]) {
            counter[s2[i]] = 0
        }
        --counter[s2[i]] // Decrement count for s2
    }

    // Check if all values are zeros
    return Object.values(counter).every((e) => (e === 0))
}

It’s a bit tedious to assign default zero values in lines 17 and 22. We can automatically set defaults by modifying the get handler of the object using Proxy objects.

The Proxy object allows us to create an object that can be used in place of the original object, but which may redefine fundamental Object operations like getting, setting, and defining properties.

Using a Proxy, our modified solution would look like,

/**
 * Determines if s1 is a permutation of s2 by 
 * checking character counts
 * @param {string} s1
 * @param {string} s2
 * @returns {boolean}
 */
function isPermutation(s1, s2) {
    if (s1.length !== s2.length) {
        // Early return if lengths don't match
        return false 
    }

    const counter = new Proxy({}, {
        get(target, prop) {
            // Return a default 0 if key does not exist
            return (prop in target ? target[prop] : 0)
        }
    })

    for (let i = 0; i < s1.length; i++) {
        ++counter[s1[i]] // Increment count for s1
        --counter[s2[i]] // Decrement count for s2
    }

    // Check if all values are zeros
    return Object.values(counter).every((e) => (e === 0))
}

Time complexity	O(n)
Space complexity	O(n). The value of keys in the counter object grows with the frequency of characters in the input.

Conclusion

Determining if one string is a permutation of another is a common problem with elegant solutions. We explored two effective methods: sorting and frequency counting. Both methods are valid and useful. The choice of the method depends on the specific requirements of your application, such as the expected size of the strings and the importance of execution speed.

By understanding these techniques you can efficiently apply this knowledge to a wide range of programming challenges.

My favourite things in life don’t cost any money. It’s really clear that the most precious resource we all have is time.
Steve Jobs