4.FindDifference.md

🔍 Find the Extra Character in Two Strings

🧠 Problem Statement

Given two strings s and t, where t is generated by shuffling s and adding one extra character, find and return that extra character.

---

🧾 Example

Input:
s = "apple"
t = "atpple"

Output:
't'

Explanation:
All characters in `s` are in `t`.

---

💡 Approach & Intuition

This is a classic frequency counting problem, and we can use hashing to solve it efficiently.

We know:

• t contains all characters from s plus one additional character.
• We need to detect which character has an odd frequency after considering both s and t.

---

✅ Steps:

1. Use a hash map to count the frequency of characters from both s and t.
2. Characters that appear in both s and t will have even frequency.
3. The extra character (from t) will make its frequency odd.
4. Return the character with odd frequency.

---

🔁 Algorithm

FUNCTION findTheDifference(s, t):
    Initialize empty map<char, int> freq_map

    FOR char c in s:
        Increment freq_map[c]

    FOR char c in t:
        Increment freq_map[c]

    FOR each entry (char, count) in freq_map:
        IF count is odd:
            RETURN char

    RETURN 'a'  // Default return, though logic ensures this line shouldn't be hit

---

💻 C++ Code

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string s, string t) {
    unordered_map<char, int> mpp;

    // Count frequency of each character in s
    for (char c : s)
        mpp[c]++;

    // Count frequency of each character in t
    for (char c : t)
        mpp[c]++;

    // Find the character with an odd frequency
    for (auto i : mpp) {
        if (i.second % 2 != 0)
            return i.first;
    }

    // This line is never expected to run
    return 'a';
}

int main() {
    string s = "apple";
    string t = "atpple";

    cout << findTheDifference(s, t);  // Output: t
    return 0;
}

---

🧮 Time & Space Complexity

Complexity	Value
Time	O(n)
Space	O(1) (bounded by charset size)

• n is the length of the strings.
• Since we're dealing with characters, the space remains constant (O(26) for lowercase, O(256) for extended ASCII).

---

🧠 Additional Notes

• You can improve this by using XOR trick (bit manipulation), where a^a = 0, and 0^x = x. XORing all characters of s and t gives the extra character directly in O(n) time and O(1) space.

  char findTheDifference(string s, string t) {
      char res = 0;
      for (char c : s) res ^= c;
      for (char c : t) res ^= c;
      return res;
  }

• The hashing approach is clearer and helps build fundamental understanding for similar problems.

---

🧪 Sample Test Cases

s	t	Output
"apple"	"atpple"	'a'
"abcd"	"abcde"	'e'
"hello"	"lehloz"	'z'

---