Saturday, January 9, 2021

Find the different character in two strings

Problem: You are given two strings str1 and str2. String str2 is generated by random shuffling string str1 and then add one more letter at a random position. Return the letter that was added to str2.

Example:

Input: str1 = "abc", str2 = "cbda"
Output: "d"
Explanation: 'd' is the letter that was added.


Approach: Its a simple problem. We can simply just xor each and every element of str1 and str2 and return it. As if you see every character other than the one which is newly added will occur twice / even times.


Implementation in C#:

    public char FindTheDifference(string s, string t) 

    {

        int xor = 0;

        for (int i = 0; i < s.Length; ++i)

        {

            xor ^= (s[i] ^ t[i]);

        }

        xor ^= t[t.Length - 1];

        return (char)(xor);

    }


Complexity: O(n)

No comments:

Post a Comment