Find the Difference Problem & Solution

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.

See the find the difference problem on LeetCode.

C++ Solution

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  char findTheDifference(string s, string t) {
    unordered_map<char, int> histogram;
    
    for (int i = 0; i < s.size(); ++i) {
      if (histogram.find(s[i]) == histogram.end()) {
        histogram[s[i]] = 1;
      } else {
        ++histogram[s[i]];
      }
    }
    
    for (int i = 0; i < t.size(); ++i) {
      if (histogram.find(t[i]) == histogram.end()) {
        return t[i];
      } else if (histogram[t[i]]-- == 0) {
        return t[i];
      }
    }
    
    return 0;
  }
};

Sample Search Queries

Many Paths. Follow Yours.

Languages

Technologies

Disciplines