Find the Difference Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Google
algorithms coding Hashing Interview interviewprep LeetCode LeetCodeSolutionsViews 6103

Problem statement

In the problem “Find the Difference” we are given two strings s and t. String t is produced by randomly stuffing the characters of string s and adding one character at a random position.

our task is to find out the character which was added in string t.

Example

s = "abcd", t = "abcde"
e

Explanation:

Find the Difference Leetcode Solution

After rearranging the characters of string t it becomes “abcde”. As “abcd” is already present in string s, so the character that was added to t is “e”.

Sorting Approach for Find the Difference Leetcode Solution

If we change our perspective to see the problem then sometimes it becomes easy to solve it. like here the problem says string t is generated by shuffling string s and adding one element at a random position. So, we can see this as string t is generated by adding a  character at a random position in the string s. Now we only need to find out the position where the character of string s is not matching with the character of the string t and then we can return the character present at that position. So we will follow these steps:

  1. Sort both the string.
  2. Check character by character both the string and the point where they didn’t match is the added character and that is the answer.
  3. If all characters matched then the character at the last position of string t is our answer.

Implementation

C++ code for Find the Difference

#include <bits/stdc++.h> 
using namespace std; 
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
    
    sort(t.begin(),t.end());
    
    
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
      {
        return t[i];
      }
    }
    
    return t[t.length()-1];
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

Java code for Find the Difference

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
    char[] sortedS = s.toCharArray();
    char[] sortedT = t.toCharArray();
    Arrays.sort(sortedS);
    Arrays.sort(sortedT);
    for(int i=0;i<s.length();i++){
      if (sortedS[i] != sortedT[i]) {
        return sortedT[i];
      }
    }

    return sortedT[s.length()];
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}

e

Complexity Analysis of Find the Difference Leetcode Solution

Time complexity

The time complexity of the above code is O(nlogn) because we are sorting both the strings. Here n is the length of the given string s.

Space complexity

The space complexity of the above code is O(n) for the java solution because we are converting the strings into an array but for C++ it is O(1) because it allows in-place sorting of the sting.

Hashing Approach for Find the Difference Leetcode Solution

We will follow these steps:

  1. Create a frequency array of size 26 to store the frequency of characters. We will initialize it with 0.
  2. Traverse the string s and store the frequency of characters in the frequency array.
  3. Now traverse the string t and decrease the frequency of each character you encounter during the traversal of string t from the frequency array.
  4. At the end, traverse the frequency array and the character corresponding to the position with value one is the added character and that is the required answer.

Implementation

C++ code for Find the Difference

#include <bits/stdc++.h> 
using namespace std; 
      char findTheDifference(string s, string t) {
        int count[26] = {0};
        for(int i=0;i<s.length();i++) count[s[i]-'a']++;
        for(int i=0;i<t.length();i++) count[t[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return 'a';
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

Java code for Find the Difference

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
        int[] count = new int[26];
        char[] S = s.toCharArray(), T = t.toCharArray();
        for(int i=0;i<S.length;i++) count[S[i]-'a']++;
        for(int i=0;i<T.length;i++) count[T[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return '\0';
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}

e

Complexity Analysis of Find the Difference Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the strings only once. Here n is the length of the given string.

Space complexity

The space complexity of the above code is O(1) because we are using constant space for frequency array.

References

Translate »