algoadvance

Leetcode 389. Find the Difference

Problem Statement:

You are given two strings s and t. String t is generated by random shuffling string s and then adding one more letter at a random position.

Return the letter that was added to t.

Example:

Input: s = "abcd", t = "abcde"
Output: "e"

Clarifying Questions:

  1. Are the strings s and t always non-empty?
    • Yes, s and t are non-empty strings, with t having exactly one more character than s.
  2. Are there any constraints on the characters within the strings?
    • Both strings only contain lowercase English letters.
  3. Is there always exactly one additional character in t than in s?
    • Yes, t will always have exactly one more character than s.

Strategy:

Approach 1: Using Character Frequency Counting

  1. Initialize an empty array count of size 26 to store the frequencies of each letter (a to z).
  2. Iterate over the string s and decrement the frequency count for each character found in s.
  3. Iterate over the string t and increment the frequency count for each character found in t.
  4. Traverse the count array to find the character with a count of 1, which is the additional character in t.

Approach 2: Using XOR Bit Manipulation

  1. Initialize a variable charCode to 0.
  2. XOR all the characters of s and t. Due to the properties of XOR, characters that appear twice will cancel out and only the additional character will remain in charCode.
  3. Convert charCode to the corresponding character.

We’ll go with Approach 2 since it is more efficient and elegant.

Code:

public class Solution {
    public char findTheDifference(String s, String t) {
        int charCode = 0;
        
        for (char c : s.toCharArray()) {
            charCode ^= c;
        }
        
        for (char c : t.toCharArray()) {
            charCode ^= c;
        }
        
        return (char) charCode;
    }
}

Time Complexity:

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