Problem Name: Find the Difference
Problem Statement:
Given two strings `s` and `t`, which contain only lowercase letters. String `t` is generated by shuffling string `s` and then adding one more letter at a random position. Find the letter that was added in `t`.
Input:
Two strings `s` and `t` where `t` is `s` shuffled with one extra character.
Output:
A single character that is the additional character in `t`.
Constraints:
- The length of `s` and `t` is between 1 and 1000.
- Strings `s` and `t` contain only lowercase English letters.
Example:
Input: s = "abcd", t = "abcde"
Output: 'e'
Explanation: 'e' is the letter that was added to `t`.
Platforms:
Companies:
- Amazon
- Microsoft
Topics Covered:
Strings,
Hash Tables,
Character Counting,
Data Structures
Solution:
Algorithm:
1. Initialize an array `hash` of size 256 to store the frequency of each character.
2. Traverse string `t` and increment the frequency of each character in the `hash` array.
3. Traverse string `s` and decrement the frequency of each character in the `hash` array.
4. Traverse string `t` again and check for the character with a frequency of 1. This character is the additional character in `t`.
Code Implementation:
C:
#include <stdio.h>
#include <string.h>
char findTheDifference(char* s, char* t) {
int hash[256] = {0};
for (int i = 0; t[i] != '\0'; i++) {
hash[(unsigned char)t[i]]++;
}
for (int i = 0; s[i] != '\0'; i++) {
hash[(unsigned char)s[i]]--;
}
for (int i = 0; t[i] != '\0'; i++) {
if (hash[(unsigned char)t[i]] == 1) {
return t[i];
}
}
return '\0'; // This line will never be reached
}
C++:
class Solution {
public:
char findTheDifference(string s, string t) {
int hash[256] = {0};
for (char ch : t) {
hash[ch]++;
}
for (char ch : s) {
hash[ch]--;
}
for (char ch : t) {
if (hash[ch] == 1) {
return ch;
}
}
return '\0'; // This line will never be reached
}
};
Java:
class Solution {
public char findTheDifference(String s, String t) {
int[] count = new int[26];
for (char ch : t.toCharArray()) {
count[ch - 'a']++;
}
for (char ch : s.toCharArray()) {
count[ch - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (count[i] == 1) {
return (char) (i + 'a');
}
}
return '\0'; // This line will never be reached
}
}
Python:
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
count = [0] * 26
for char in t:
count[ord(char) - ord('a')] += 1
for char in s:
count[ord(char) - ord('a')] -= 1
for i in range(26):
if count[i] == 1:
return chr(i + ord('a'))
Complexity Analysis:
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Worst Case | O(n) | O(1) |
| Average Case | O(n) | O(1) |
| Best Case | O(n) | O(1) |
