Find difference between two strings
Given two strings, where the second string is constructed using all characters of the first string except one, find the character that was skipped in the second string.
For example,
Output: b
Input: first = ‘a’, second = ”
Output: a
You may assume valid input.
A simple solution is to store the count of each character of the second string in a map. Then, for each character in the first string, decrease its count. If the count of any character becomes negative at any point in time, we can say that the character is missing from the second string. However, this solution doesn’t take advantage of the fact that the second string is constructed from the first string, with only a single character skipped.
1. Using XOR of ASCII codes
The idea is to take the XOR of the ASCII codes of all characters in both strings. Since characters that occur twice cancel each other out, the result will be the ASCII code of the missing character. This will work on a valid input that satisfies the problem constraints.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; char findDiff(string first, string second) { char c = 0; for (char ch: first) { c ^= ch; } for (char ch: second) { c ^= ch; } return c; } int main() { string first = "abc"; string second = "ac"; cout << findDiff(first, second); return 0; } |
Output:
bb
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { public static char findDiff(String first, String second) { char c = 0; for (char ch: first.toCharArray()) { c ^= ch; } for (char ch: second.toCharArray()) { c ^= ch; } return c; } public static void main(String[] args) { String first = "abc"; String second = "ac"; System.out.println(findDiff(first, second)); } } |
Output:
b
Python
The time complexity of the above solution is O(n), where n is the length of the first string. However, it uses two loops. The code can be optimized to run in a single loop, since the second string has just one character less than the first string. Here’s an optimized version of the above solution that processes both strings in a single iteration:
C++
|
1 2 3 4 5 6 7 8 |
char findDiff(string first, string second) { char c = first[first.length() - 1]; for (int i = 0; i < second.length(); i++) { c ^= first[i] ^ second[i]; } return c; } |
Java
|
1 2 3 4 5 6 7 8 |
public static char findDiff(String first, String second) { char c = first.charAt(first.length() - 1); for (int i = 0; i < second.length(); i++) { c ^= first.charAt(i) ^ second.charAt(i); } return c; } |
Python
|
1 2 3 4 5 6 |
def findDiff(first, second): c = ord(first[-1]) for i in range(len(second)): c ^= ord(first[i]) ^ ord(second[i]) return chr(c) |
2. Using Sum of ASCII codes
Another option is to keep track of the sum of the ASCII codes for each character in the second string. Then, deduct the ASCII code of each character of the first string from the total. At the end, all that is left is the ASCII code of the missing character from the second string.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; char findDiff(string first, string second) { int sum = 0; for (char ch: first) { sum += ch; } for (char ch: second) { sum -= ch; } return sum; } int main() { string first = "abc"; string second = "ac"; cout << findDiff(first, second); return 0; } |
Output:
b
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Main { public static char findDiff(String first, String second) { int sum = 0; for (char ch: first.toCharArray()) { sum += ch; } for (char ch: second.toCharArray()) { sum -= ch; } return (char) sum; } public static void main(String[] args) { String first = "abc"; String second = "ac"; System.out.println(findDiff(first, second)); } } |
Output:
b
Python
The time complexity of the above solution is O(n). As with the previous solution, the code can be further optimized to run in a single loop.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)