Merakesh
Education

Javascript Solution Find the Difference

In this article we will solve leetcode problem `Find the Difference' using Bit Manipulation.

rakesh

rakesh

@jsbugpost

Javascript Solution Find the Difference

Problem Overview

There are two string s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

We have to return added letter.

For exact problem visit Leetcode Link;

Sample Input Output

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Javascript Solution

Essentially we will be taking advantage of the Bitwise XOR ^ operator. For every NUMBER X, we have

X^X=0 and X^0=X So the plan is:

  1. Iterate over the shortest array s
  2. Keep accumulating (XOR ^ing) the elements of both s and t, after we have converted them to Numbers with CharCodeAt() so the XOR can work. Elements that appear both in t and s will give us zero ( X^X=0), yet that zero will not affect the total sum (X^0=X)
  3. Return the converted back to character final sum, which is essentially the (desired) character not present in s
leetcode submission result

Original Solution Link GeorgeChryso;

const findTheDifference = function(s, t) {
    let sum=0 // initialize the accumulator
 
	// t.length > s.length because there will always be 1 extra letter on t (the one we want to return)
    for (let i = 0; i < s.length; i++) {
		sum^=                       // accumulate with XOR
		t[i].charCodeAt()^          // the converted to Number t[i]
        s[i].charCodeAt()           // along with a converted to Number s[i],
 
    }
    sum^=t[i].charCodeAt()          // add the remaining letter of t
   return String.fromCharCode(sum)  // return the converted to Character total
 
};
 
Quick example:
s='abcd' , t='dcbqa'

Same Algorithm Implementation Using ES6

/**
 * @param {number} x
 * @return {number}
 */
var findTheDifference = function (s, t) {
  return String.fromCharCode(
    [...s, ...t].reduce((acc, c) => {
      return acc ^ c.charCodeAt(0)
    }, 0)
  )
}

More Articles

Deploying Next.js Apps

How to deploy your Next.js apps on Vercel.

January 2, 2023

How to show CHANGELOG page in storybook of react, typescript project

In this blog post, we'll go over the steps for showing a CHANGELOG page in your Storybook instance. By the end, you'll have a clear understanding of how to set this up and keep your CHANGELOG up to date.

December 20, 2022