Find the Difference

Problem Description

You are given two strings s and t.

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

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• $0 <= s.length <= 1000$
• $t.length == s.length + 1$
• $s and t consist of lowercase English letters.$

Algorithm

1. For each character i in t, it checks if the count of i in t is greater than the count of i in s. If this condition is met, it means that i is the extra letter that was added to t, so it returns i and breaks out of the loop.

Code Implementation

Python:

class Solution(object):
  def findTheDifference(self, s, t):
    for char in t:
      if t.count(char) > s.count(char):
        return char

C++:

#include <unordered_map>

char findTheDifference(std::string s, std::string t) {
  std::unordered_map<char, int> char_counts;
  for (char c : s) {
    char_counts[c]++;
  }
  for (char c : t) {
    if (char_counts.find(c) == char_counts.end() || char_counts[c] == 0) {
      return c;
    }
    char_counts[c]--;
  }
  return '\0'; // Return null character if no difference found
}

Java:

public class Solution {
  public char findTheDifference(String s, String t) {
    HashMap<Character, Integer> char_counts = new HashMap<>();
    for (char c : s.toCharArray()) {
      char_counts.put(c, char_counts.getOrDefault(c, 0) + 1);
    }
    for (char c : t.toCharArray()) {
      if (!char_counts.containsKey(c) || char_counts.get(c) == 0) {
        return c;
      }
      char_counts.put(c, char_counts.get(c) - 1);
    }
    return '\u0000'; // Return null character if no difference found (Unicode representation)
  }
}

JavaScript:

function findTheDifference(s, t) {
  const char_counts = {};
  for (const char of s) {
    char_counts[char] = (char_counts[char] || 0) + 1;
  }
  for (const char of t) {
    if (!(char in char_counts) || char_counts[char] === 0) {
      return char;
    }
    char_counts[char]--;
  }
  return ""; // Return empty string if no difference found
}