Find the Difference Leetcode Solution

In this problem, we are given two strings. The second string is generated by shuffling the characters of the first string randomly and then adding an extra character at any random position. We need to return the extra character that was added to the second string. The characters will always be lower-case English letters.

Example

a = "abcde" , b = "ebacdf"

f

a = "aaaa" , b = "aaaaa"

a

Explanation #1

The extra character that is added to string b is ‘f’ as string a doesn’t contain it.

Explanation #2

String a has 4 ‘a’ letters while string b has 5. So, the extra letter is ‘a’.

Approach(Sorting)

We can sort both the strings and then iterate both of them letter by letter to find the first position where they differ. The second string will always have one extra character. So, we will always find a point where string a and b differs. However, there can be a case where string b after sorting matches every character in string a in but has one extra character in the end. We need to handle this one special case.

Algorithm

1. Sort both the strings, a and b. As it is not possible in java, we first convert them into char arrays
2. For every character present in the shorter string, we do a letter-by-letter check:
   • If the character in string a is not equal to the corresponding character in string b:
     • return this character.
3. Return the last character of string b as it is the extra character
4. Print the result

Implementation of Find the Difference Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java Program

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}

f

Complexity Analysis of Find the Difference Leetcode Solution

Time Complexity

O(NlogN), where N = Length of the longer string. We sort the strings/char arrays which take O(NlogN) time.

Space complexity

O(N) in java and O(1) in C++ as we convert the strings into char Arrays in java.

Approach(Hashing)

In both the strings, we can hash every character with its frequency and find the character that differs in frequency. Since we have a constant number of unique characters. This algorithm is faster than the one discussed above. As an efficient implementation, we can create a hash table and increment the frequency for every character in string a and decrement the frequency for every character in string b. This will leave us in a case where the frequency of exactly one character is non-zero and this will be the extra character in string b.

Algorithm

1. Initialize a hash table to store the frequency of all characters as frequency
2. For every character in string a:
   • increment its frequency in the hash table
3. For every character in string b:
   • decrement its frequency in the hash table
   • If its frequency is equal to -1:
     • return this character
4. Return ‘-‘ to maintain function syntax
5. Print the result

Implementation of Find the Difference Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java Program

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}

f

Complexity Analysis of Find the Difference Leetcode Solution

Time Complexity

O(N), N = size of the longer string, as we traverse through both the strings once to update their character frequencies.

Space complexity

O(1). Though we use a hashtable to store characters with their frequencies, we use constant space irrespective of the input. So, the space complexity is constant.