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