Find the Difference - Practice Coding Problems

Find the Difference - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcd", t = "abcde"

› Output: "e"

💡 Note: The letter 'e' was added to the end of string s to create string t.

Example 2 — Added in Middle

$ Input: s = "abc", t = "abcd"

› Output: "d"

💡 Note: The letter 'd' was added to string s. Even though t is shuffled, we can detect the extra character.

Example 3 — Single Character

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

› Output: "y"

💡 Note: Edge case: empty string s, and t contains only the added character 'y'.

Constraints

0 ≤ s.length ≤ 1000
t.length == s.length + 1
s and t consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Original

Start with string s

Shuffle + Add

Shuffle s and add one character

Find Extra

Identify the added character

Key Takeaway

🎯 Key Insight: XOR cancels identical characters, leaving only the unique added character

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that we need to find the one character that appears differently between two strings. The XOR approach is most elegant since identical characters cancel out, leaving only the added character. Best approach: XOR bit manipulation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Compare	O(n log n)	O(n)	Sort both strings and compare character by character to find the difference
Character Counting with Arrays	O(n + m)	O(1)	Count frequency of each character in both strings and find the difference
Hash Map Frequency Count	O(n + m)	O(1)	Use hash map to count character frequencies and find the difference
XOR Bit Manipulation	O(n + m)	O(1)	XOR all characters from both strings - identical characters cancel out

Sort and Compare — Algorithm Steps

Sort both strings
Compare character by character
Return the first different character or extra character

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Both

Sort s and t: "abc" and "abcd"

Compare

Compare character by character

Find Extra

First mismatch or end of shorter string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

char solution(char* s, char* t) {
    int lenS = strlen(s);
    int lenT = strlen(t);
    
    qsort(s, lenS, sizeof(char), compare);
    qsort(t, lenT, sizeof(char), compare);
    
    for (int i = 0; i < lenS; i++) {
        if (s[i] != t[i]) {
            return t[i];
        }
    }
    
    return t[lenT - 1];
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    char result = solution(s, t);
    printf("%c\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Dominated by sorting both strings where n is the length

⚡ Linearithmic

Space Complexity

O(n)

Space needed to create sorted copies of the strings

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Compare — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler