Check Permutation - Online Learning Platform

Data structures and Algorithms in Javascript

About Lesson

We will address the following Topics

Question

Given two strings s1 and s2, create a function to determine whether they are permutations of each other. Return true if they are or else false.

Explanation

The question is asking to determine if two given strings have the same characters but may be arranged differently.

Examples

Example 1:

Input: "listen", "silent"
Output: true
Explanation: returns true because all listen when rearranged forms the word silent.

Example 2:

Input: "hello", "world"
Output: false
Explanation: returns false because hello and world are not permutations of each other.

Constraints

Comparison is case-sensitive.
whitespace is significant (considered). So, "god " is different from "dog".

Practice

Accordion #1

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Hint

Strings of different lengths cannot have the same permutation.
Utilize a character frequency hashmap to track characters in the strings.
Ensure the character count doesn’t exceed 128 to maintain efficient time and space complexity – O(N) for time and O(1) for space.

/** * Given two strings, create a function to determine whether they are permutations of each other. * @param {string} str1 * @param {string} str2 * @return {boolean} */ const checkPermutation = (str1, str2) => { }; // some Tests from here const assert = require("assert") // Test 1: Given two strings with unequal chars, it should return false const test1Result = checkPermutation('mississippi', 'ppissssiim'); assert.strictEqual(test1Result, false, 'Test 1 failed'); // Test 2: Given two empty strings, it should return true const test2Result = checkPermutation('', ''); assert.strictEqual(test2Result, true, 'Test 2 failed'); // Test 3: Given two strings with no permutation, it should return false const test3Result = checkPermutation('mississippi', 'ppissisiimy'); assert.strictEqual(test3Result, false, 'Test 3 failed'); // Test 4: Given two strings with permutation, it should return true const test4Result = checkPermutation('mississippi', 'ppissssiimi'); assert.strictEqual(test4Result, true, 'Test 4 failed'); // Test 5: Given two strings with same chars but with space, it should return false const test5Result = checkPermutation('god ', 'dog'); assert.strictEqual(test5Result, false, 'Test 5 failed'); console.log('All tests passed.');

Solution

Accordion #1

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

See Solution

There are multiple ways you can solve this.

Method 1: Using sorting

The function checks if two strings have the same length, makes them an array, and sorts them. Then convert into string again using join and compare both strings to be equal.

Time Complexity: O(NLogN)
Auxiliary space: O(N)

Method 2: Count Characters

Create a counting array of size 256 to track character frequencies in two strings, check if their lengths are equal, and iterate through the counting arrays to determine if the strings are permutations of each other. This is best in terms of time and space complexity.

Time Complexity: O(N)
Auxiliary space: O(1) as the size of the counting array (256) is constant.

Method 3: Using Map
This is not the most efficient in terms of space complexity but it is easier to understand.

const checkPermutation = (str1, str2) => {
  // check if length of strings is not equal
  if (str1.length !== str2.length) return false;

  // build a map of char count for str1
  const charMap = {};
  for(const currentChar of str1) {
    if(!charMap[currentChar]) {
      charMap[currentChar] = 1;
    } else {
      charMap[currentChar] += 1;
    }
  }

  // reduce char count for each char found in str2
  for(const currentChar of str2) {
    if(!charMap[currentChar]) {
      return false;
    }
    charMap[currentChar] -= 1;
  }
  return true
};

Explanation

First, we verify if the lengths of both strings are the same; if not, we conclude they cannot be permutations and return false.
Next, we utilize a Map to maintain the character frequencies of the first string (str1).
We then iterate through the second string (str2) and decrement the corresponding frequencies in the Map.
If a character is absent in the Map or its frequency reaches zero during this process, we return false.
If we successfully match all characters in str2, the Map becomes empty, and we return true.

Time Complexity: O(N)
Space Complexity: O(S), where S is number of unique characters.