Codeforces Round #479 (Div. 3) - B - Two-gram

1. 문제

B. Two-gram

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Two-gram is an ordered pair (i.e. string of length two) of capital Latin letters. For example, "AZ", "AA", "ZA" — three distinct two-grams.

You are given a string $s$ consisting of $n$ capital Latin letters. Your task is to find any two-gram contained in the given string as a substring(i.e. two consecutive characters of the string) maximal number of times. For example, for string $s$ = "BBAABBBA" the answer is two-gram "BB", which contained in $s$ three times. In other words, find any most frequent two-gram.

Note that occurrences of the two-gram can overlap with each other.

Input

The first line of the input contains integer number $n$ ($2\le n\le 100$) — the length of string $s$. The second line of the input contains the string $s$ consisting of $n$ capital Latin letters.

Output

Print the only line containing exactly two capital Latin letters — any two-gram contained in the given string $s$ as a substring (i.e. two consecutive characters of the string) maximal number of times.

Examples

input

7
ABACABA

output

AB

input

5
ZZZAA

output

ZZ

Note

In the first example "BA" is also valid answer.

In the second example the only two-gram "ZZ" can be printed because it contained in the string "ZZZAA" two times.

2. 알고리즘

키워드 - 구현

접근법 - 주어지는 문자열에 PAIR 를 찾는 문제

1번 예제에서 

AB = 2

BA = 2

AC = 1

CA = 1

AB, BA 가 답이며 둘중에 아무거나 출력 해도 된다.

3. 코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>         // greater 사용 위해 필요  
#include <string>
#include <map>
#include <math.h>
using namespace std;
 
int main() {
 
    int n; cin >> n;
    string s; cin >> s;
 
    map<string, int> mm;
    for(int i=0; i<n; i++) {
 
        if (i+1 < n) {
            string ss;
            ss.push_back(s[i]);
            ss.push_back(s[i+1]);
            mm[ss]++;
        }
    }
 
    map<string, int>::iterator iter;
 
    iter = mm.end();
 
    int sol = -1;
    string sss;
    for(iter = mm.begin(); iter != mm.end(); iter++) {
        if (sol < iter->second) {
            sol = iter->second;
            sss.clear();
            sss.append(iter->first);
        }
    }
 
    cout << sss << endl;
    return 0;
}