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

 

- Sort both the strings, a and b. As it is not possible in java, we first convert them into char arrays

- 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.

 

www.tutorialcup.com/leetcode-solutions/find-the-differenc...

Done