All Tracks Algorithms String Algorithms String Searching Problem

Hamming
Tag(s):

Algorithms, Easy

Problem
Editorial
Analytics

It is Raful's birthday, and his friends gave him N strings of length M. But he is not happy, because he wants only one beautiful string S.

His friends are upset now. You, as the best programmer in Lalalandia, decided to help them.

The string S is considered beautiful only when the sum of the Hamming distances between it and each of the N strings is minimal. If there exist several such strings, print out the lexicographically smallest one.

Input format

The first line of the input contains two integers N, M - number of strings and their lengths respectively.

Then N lines follow, each containing a string \(s_i\) (\(1 \le i \le N\)), each consists of lowercase English letters.

Output format

The only line of the output should contain the string S.

Constraints:

\(1 \le N * M \le 100000\)

Note

You can learn more about Hamming distance here:

https://en.wikipedia.org/wiki/Hamming_distance

SAMPLE INPUT
4 1
a
b
c
d
SAMPLE OUTPUT
a
Explanation

In this sample, "a" is lexicographically minimal string among all valid answers.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?