easy Find the Difference

Problem Statement

You are given two strings s and t. The string t is formed by taking the string s, randomly shuffling all its characters, and then adding one additional character at a random place.

Return the extra character that was added to t.

Examples

• Example 1:

  • Input: s = "a", t = "aa"
  • Expected Output: "a"
  • Justification: The string t contains an extra "a" compared to the string s.

• Example 2:

  • Input: s = "xyz", t = "yxzz"
  • Expected Output: "z"
  • Justification: Besides the characters in s, t has an additional "z".

• Example 3:

  • Input: s = "lampump", t = "lumpmpap"
  • Expected Output: "p"
  • Justification: After shuffling s and adding an extra character, t includes one more "p" than s.

Solution

To solve this problem, we will use a character frequency count approach. This method involves counting the frequency of each character in both strings s and t, and then comparing these frequencies to find the character that is extra in t.

This approach is effective because, by identifying the character with a frequency discrepancy, we can pinpoint the additional character in t. This method ensures accuracy regardless of the shuffle, as the order of characters does not impact the frequency count. The simplicity and directness of comparing character frequencies make this approach not only intuitive but also efficient for identifying the added character.

Step-by-Step Algorithm

1. Initialize a Frequency Counter: Start by creating a data structure (like a hash map or dictionary) to keep track of the frequency of each character in the strings s and t. This will allow us to count how many times each character appears in both strings.

2. Count Frequencies in s: Iterate through each character in the string s. For each character, increase its count in the frequency counter by 1. This step helps us understand the composition of s in terms of its characters.

3. Identify the Extra Character in t: Now, iterate through each character in the string t. Decrease its count in the frequency counter by 1 for each occurrence. If at any point, the count for a character goes negative, it indicates that this character is the additional one in t (since it appears more times in t than in s).

4. Return the Extra Character: The moment you identify a character whose count goes negative, return it. This character is the one that was added to s to form t.

Algorithm Walkthrough

Let's walk through the algorithm using the given strings s = "lampump" and t = "lumpmpap".

1. Initialize Frequency Map: Start with an empty map.

   {}

2. Count Characters in s:

   • For 'l': {'l': 1}
   • For 'a': {'l': 1, 'a': 1}
   • For 'm': {'l': 1, 'a': 1, 'm': 1}
   • For 'p': {'l': 1, 'a': 1, 'm': 1, 'p': 1}
   • For 'u': {'l': 1, 'a': 1, 'm': 1, 'p': 1, 'u': 1}
   • For 'm': {'l': 1, 'a': 1, 'm': 2, 'p': 1, 'u': 1} (incrementing 'm')
   • For 'p': {'l': 1, 'a': 1, 'm': 2, 'p': 2, 'u': 1} (incrementing 'p')

3. Adjust Counts for Characters in t:

   • For 'l': {'l': 0, 'a': 1, 'm': 2, 'p': 2, 'u': 1}
   • For 'u': {'l': 0, 'a': 1, 'm': 2, 'p': 2, 'u': 0}
   • For 'm': {'l': 0, 'a': 1, 'm': 1, 'p': 2, 'u': 0}
   • For 'p': {'l': 0, 'a': 1, 'm': 1, 'p': 1, 'u': 0}
   • For 'm': {'l': 0, 'a': 1, 'm': 0, 'p': 1, 'u': 0}
   • For 'p': {'l': 0, 'a': 1, 'm': 0, 'p': 0, 'u': 0}
   • For 'a': {'l': 0, 'a': 0, 'm': 0, 'p': 0, 'u': 0}
   • For 'p': {'l': 0, 'a': 0, 'm': 0, 'p': -1, 'u': 0} (Now, 'p' count is -1, which indicates 'p' is the added character)

4. Identify the Added Character: Since the frequency of 'p' went to -1, we conclude that 'p' is the character added to t. Hence, 'p' is returned as the added character.

Code

import java.util.HashMap;

public class Solution {

  // Method to find the added character
  public char findTheDifference(String s, String t) {
    // Creating a map to store the frequency of characters
    HashMap<Character, Integer> freq = new HashMap<>();
    // Increment frequency based on characters in s
    for (char c : s.toCharArray()) {
      freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    // Decrement frequency based on characters in t and find the extra character
    for (char c : t.toCharArray()) {
      freq.put(c, freq.getOrDefault(c, 0) - 1);
      if (freq.get(c) == -1) {
        return c;
      }
    }
    // Return a space character if nothing is found (should never happen in valid inputs)
    return ' ';
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Testing the examples
    System.out.println(solution.findTheDifference("a", "aa")); // Example 1
    System.out.println(solution.findTheDifference("xyz", "yxzz")); // Example 2
    System.out.println(solution.findTheDifference("lampump", "lumpmpap")); // Example 3
  }
}

Complexity Analysis

Time Complexity

The time complexity for all implementations is , where (n) is the length of the longer string (t). This is because each character in both strings s and t is visited exactly once to increment or decrement their count in the frequency map or object.

Space Complexity

The space complexity is in terms of the extra space used by the frequency map. Although the size of the map depends on the number of distinct characters, since the input is limited to lowercase or uppercase letters of the English alphabet, the maximum size of the map is constrained to a constant value (26 for either lowercase or uppercase exclusively, 52 if both cases are considered).