Official

B - The Odd One Out Editorial by en_translator


There are several approaches for this problem.

Approach 1. Count the occurrences of each letter

If we count the frequency of each letter, the letter occurring exactly once is unique, so we can print it.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  map<char,int> mp;
  for(auto &nx : s){ mp[nx]++; }
  for(auto &nx : mp){
    if(nx.second==1){
      cout << nx.first << "\n";
    }
  }
  return 0;
}

Approach 2. Use the property of the problem

When the characters of the given string is sorted lexicographically, the answer letter always falls into the beginning or the end.
More specifically, the sorted string \(S'\) satisfies the following:

  • if the \(1\)-st and \(2\)-nd character of \(S'\) are different, the answer is the \(1\)-st character of \(S'\);
  • otherwise, the answer is the last character of \(S'\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  if(s[0]!=s[1]){cout << s[0] << "\n";}
  else{cout << s.back() << "\n";}
  return 0;
}

posted:
last update: