algoadvance

Leetcode 389. Find the Difference

Problem Statement

LeetCode Problem 389: Find the Difference

You are given two strings s and t.

String t is generated by randomly shuffling string s and then adding one more letter at a random position.

Return the letter that was added to t.

Example:

Constraints:

Clarifying Questions

  1. Can s be an empty string?
    • Yes, s can be an empty string, and in that case, t will have one letter.
  2. Do we need to worry about non-alphabet characters?
    • No, the problem states that s and t consist of lowercase English letters only.
  3. What if the strings are very large?
    • The problem constraints ensure that s.length is at most 1000. Performance should be considered within these constraints.

Strategy

Approach:

We can solve this problem efficiently using the following methods:

  1. Counting Characters Approach:
    • Use an array to count occurrences of each character in s and t.
    • The extra character in t will have a count difference due to being added.
  2. Bit Manipulation (XOR) Approach:
    • Use the XOR operation to find the different character.
    • XORing all characters in both strings will cancel out the characters that appear twice (i.e., those in s and t), and only the extra character will remain.

Implementation:

We’ll use the bit manipulation approach for its simplicity and efficiency.

Code

#include <iostream>
#include <string>

char findTheDifference(std::string s, std::string t) {
    char res = 0;
    for(char c : s) {
        res ^= c;
    }
    for(char c : t) {
        res ^= c;
    }
    return res;
}

int main() {
    std::string s = "abcd";
    std::string t = "abcde";
    std::cout << "The added letter is: " << findTheDifference(s, t) << std::endl; // Output: e
    return 0;
}

Time Complexity

The time complexity for this solution is O(n), where n is the length of string s (and by extension, t is n+1). This is because we are iterating through all characters in both strings exactly once.

The space complexity is O(1) since we are using a constant amount of extra space.

This approach ensures an efficient and clear solution to the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI