Indian National Olympiad in Informatics

Related:

Online Programming Contest, 2-3 April 2005

IARCS home > OLYMPIAD

Basic Division

Problem 1: Overlapping Subwords, (K Narayan Kumar, CMI)

In this problem we are concerned with words constructed using the lowercase letters of the English alphabet (that is, a,b,c,...,z). A word need not be meaningful - for us, any sequence of letters is a word. For example, abbca is a word.

A subword of a word is a contiguous subsequence of the word. For example the subwords of the word abbba are a, b, ab, bb, ba, abb, bbb, bba, abbb, bbba and abbba.

The word b appears thrice as a subword of abbba (when we break it up as a b bba, ab b ba and abb b a. We call these the (three) instances of the subword b in abbba.

On the other hand, the word bb appears twice as a subword of abbba (corresponding to a bb ba and ab bb a). Notice that the two instances of bb in abbba are overlapping, the middle b appears in both of them. We are interested in words that have overlapping subwords.

Here are a couple of examples:

The word abbababbabbab has overlapping subwords. The subword abbab has three instances in this word -- abbab abbabbab, abbab abbab bab and abbababb abbab -- of which the last two instances overlap.
On the other hand, the word abbabaabbab has no overlapping subwords.

Your task is to determine whether a given word has overlapping subwords.

Input format

The first line of the input will contain a single integer N, indicating the number of letters in the given word. The next line contains a sequence of N letters drawn from a,b,...,z.

Output format

If there are overlapping subwords, the first line of the output should be YES. In this case, the second line should contain a single word w that has overlapping instances in the given word. If there are multiple such words, it suffices to print one. If there are no overlapping subwords, the output should consist of a single line with the word NO.

Test data

You may assume 1 ≤ N &le 200.

Example

We now illustrate input and output formats using the examples described above.

Sample input 1:

5
abbba

Sample output 1:

YES
bb

Sample input 2:

11
abbabaabbab

Sample output 2:

NO

Sample input 3:

13
abbababbabbab

Sample output 3:

YES
abbab