Sponsored
Sponsored
This approach involves creating frequency counts for both strings. Loop through each character in both strings, updating a counter for each character. By comparing these counters, you can determine which character has a different count, revealing the additional character in string t.
The time complexity is O(n) where n is the length of s as we iterate over t once in the worst case. Space complexity is O(1) because the storage requirement is constant (the fixed size count array).
1import java.util.HashMap;
2
3public class FindDifference {
4 public char findTheDifference(String s, String t) {
5 HashMap<Character, Integer> count = new HashMap<>();
6 for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) + 1);
7 for (char c : t.toCharArray()) {
8 count.put(c, count.getOrDefault(c, 0) - 1);
9 if (count.get(c) < 0) return c;
10 }
11 return '\0';
12 }
13
14 public static void main(String[] args) {
15 FindDifference fd = new FindDifference();
16 System.out.println(fd.findTheDifference("abcd", "abcde")); // Output: e
17 System.out.println(fd.findTheDifference("", "y")); // Output: y
18 }
19}This solution utilizes a HashMap to keep a frequency count of the characters in string s. For each character in t, it decreases the count and checks for a character whose count becomes negative, which indicates it's the extra character.
This approach leverages the properties of the XOR bitwise operator. XOR'ing the same numbers results in 0 and XOR is commutative and associative, meaning the order of operations doesn't matter. By XOR'ing all characters in both strings, one additional character will be left out, since all others cancel each other out.
Time complexity is O(n) as both strings are traversed. Space complexity is O(1) because only a single variable is used.
1using namespace std;
char findTheDifference(string s, string t) {
char diff = 0;
for (char c : s) diff ^= c;
for (char c : t) diff ^= c;
return diff;
}
int main() {
cout << findTheDifference("abcd", "abcde") << endl; // Output: e
cout << findTheDifference("", "y") << endl; // Output: y
return 0;
}The C++ solution uses a single variable to XOR all characters from both strings. Characters that appear twice (once in each string equally) will zero out, and only the additional character in t remains.