389. Find the Difference

EasyBit ManipulationHash TableStringSorting

Problem Description

You are given two strings, s and t. The string t is formed by taking the string s, performing a random shuffle of its characters, and then adding one additional character at a random position in the string. Your task is to find the letter that was added to t.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The intuition behind the solution is to use a character count approach. First, the solution counts the frequency of each character in string s. Then it iterates through string t and decrements the count for each character encountered. Since string t contains all characters from s plus one extra, the moment we find a character in t such that its count drops below zero, we know that this is the extra character that was added—it wasn’t present in s in the same quantity.

Therefore, by using a hash map or an array for counting the characters, we can efficiently find the added character.

Learn more about Sorting patterns.

Solution Approach

The solution provided uses Python's Counter class from the collections module, which is essentially a hash map or dictionary that maps elements to the number of occurrences in a given iterable.

Here's a step-by-step breakdown of how the algorithm works:

cnt = Counter(s): We initialize cnt with the counts of each character in string s.
We then iterate over each character c in string t with for c in t:. As t includes every character from s plus one additional character, we expect all counts to be zero or one by the end of this iteration.
Inside the loop, we decrement the count of the current character cnt[c] -= 1. Since t should have exactly the same characters as s, except for the added one, most of the counts should eventually become zero.
The condition if cnt[c] < 0: checks if the count of the current character goes below zero. This indicates that c has appeared one more time in t than it has in s, specifically identifying it as the extra character.
At this point, the algorithm immediately returns c with return c, which is the character that was added to t.

By leveraging the Counter data structure, the algorithm can operate efficiently and arrive at the solution in O(n) time, where n is the length of the string t.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume the given strings are s = "aabc" and t = "aacbc". We need to identify the letter that was added to t.

Following the steps provided in the solution approach:

We first initialize cnt with the counts of each character in string s. That gives us a Counter object with counts { 'a': 2, 'b': 1, 'c': 1 }.
We then iterate over each character in t. The sequence of actions in the loop would look like this:
- For c = 'a', decrement cnt[c] to { 'a': 1, 'b': 1, 'c': 1 }.
- For c = 'a' again, decrement cnt[c] to { 'a': 0, 'b': 1, 'c': 1 }.
- For c = 'c', decrement cnt[c] to { 'a': 0, 'b': 1, 'c': 0 }.
- For c = 'b', decrement cnt[c] to { 'a': 0, 'b': 0, 'c': 0 }.
- Lastly, for c = 'c', decrement cnt[c] which would result in { 'a': 0, 'b': 0, 'c': -1 }.
As soon as we decrement a count and it drops below zero, we've found our character. In this example, when we encounter the second 'c' in t, cnt[c] becomes -1, which means 'c' is the added character.

Thus, we return 'c' as the character that was added to t. The algorithm effectively determines that 'c' is the letter that was added, doing so with a simple linear scan and character count adjustment.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def findTheDifference(self, s: str, t: str) -> str:
5        # Create a counter for all characters in string 's'
6        char_count = Counter(s)
7      
8        # Iterate through each character in string 't'
9        for char in t:
10            # Decrement the count for the current character
11            char_count[char] -= 1
12          
13            # If count becomes less than zero, it means this character is the extra one
14            if char_count[char] < 0:
15                return char
16      
17        # The function assumes that it is guaranteed there is an answer
18        # If all characters match, this line would theoretically not be reached
19

1class Solution {
2    public char findTheDifference(String s, String t) {
3        // Array to store the count of each alphabet character in string s
4        int[] count = new int[26];
5      
6        // Increment the count for each character in the first string s
7        for (int i = 0; i < s.length(); i++) {
8            count[s.charAt(i) - 'a']++;
9        }
10      
11        // Iterate over the second string t
12        for (int i = 0; i < t.length(); i++) {
13            // Decrease the count for the current character
14            // If the count becomes negative, we've found the extra character in t
15            if (--count[t.charAt(i) - 'a'] < 0) {
16                return t.charAt(i);
17            }
18        }
19      
20        // This return statement is a placeholder; the code logic guarantees that the function will return from within the loop.
21        // Since we know string t has one extra character, the loop will always return that extra character before this point.
22        // Thus, the code will never reach this statement, but Java syntax requires a return statement here.
23        return '\0';
24    }
25}
26

1class Solution {
2public:
3    char findTheDifference(string s, string t) {
4        int charCounts[26] = {0}; // Initialize an array to keep track of the character counts from 'a' to 'z'.
5      
6        // Increment the count for each character in string 's'.
7        for (char& c : s) {
8            charCounts[c - 'a']++; // 'c - 'a'' translates char c to an index (0-25) corresponding to chars 'a'-'z'.
9        }
10      
11        // Decrement the count for each character in string 't'.
12        for (char& c : t) {
13            charCounts[c - 'a']--; // Similarly, translate char c to the correct index.
14          
15            // If the count goes below zero, it means 't' has an extra character that is not in 's'
16            if (charCounts[c - 'a'] < 0) {
17                return c; // Return the extra character.
18            }
19        }
20      
21        // If no extra character is found, this shouldn't happen as per the problem statement,
22        // but we return a space as a default return value.
23        return ' ';
24    }
25};
26

1function findTheDifference(source: string, target: string): string {
2    // Convert the 'target' string into an array of its characters,
3    // then use the 'reduce' function to accumulate the sum of the char codes.
4    const targetCharCodeSum = [...target].reduce((runningTotal, currentChar) => 
5        runningTotal + currentChar.charCodeAt(0), 0
6    );
7
8    // Convert the 'source' string into an array of its characters,
9    // then use the 'reduce' function to accumulate the sum of the char codes.
10    const sourceCharCodeSum = [...source].reduce((runningTotal, currentChar) => 
11        runningTotal + currentChar.charCodeAt(0), 0
12    );
13
14    // Find the difference in the accumulated char code sums between the 'target' and 'source' strings.
15    // This difference is the char code of the added letter in the 'target' string.
16    const charCodeDifference = targetCharCodeSum - sourceCharCodeSum;
17
18    // Convert the char code of the added letter to a string and return it.
19    return String.fromCharCode(charCodeDifference);
20}
21

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n) where n is the length of the string t. This is because the code iterates over each character of the string t exactly once. Utilizing the Counter from the collections module on string s has a time complexity of O(m), where m is the length of string s. Thus, the overall time complexity of the algorithm is O(m + n).

Space Complexity

The space complexity of the function is also O(n), with n being the size of the alphabet used in the strings because the Counter object cnt will store the frequency of each character present in string s. In the worst-case scenario where all characters are unique, the counter will need to store an entry for each character. Since the alphabet size is generally fixed and small (e.g., 26 for lowercase English letters), the space complexity could also be considered O(1) if we consider the alphabet size as a constant factor.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems