The maximum substring

3.3

10 votes
Algorithms, String Manipulation
Problem

You are given a string s consisting only of lowercase letters. A substring [l; r] of s is a string s[l...r] and its length is equal to rl+1. Find the substring of s that contains a maximum number of occurrences.

If several answers exist, then print the one with the maximum length. If there are still several answers, then print the one with the minimum index of the first occurrence.

Input format

The single line contains string s (1|s|105).

Output format

Find the suitable substring.

 

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

There are 2 occurrences both of "xyz" and "abc". Since first occurrence of "xyz" is position 1, answer xyz. 

Editor Image

?