All Tracks Algorithms String Algorithms String Searching Problem

The maximum substring
/

Algorithms, String Algorithms, String Searching

Problem
Editorial
Analytics

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 \(r-l+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 \le |s| \le 10^5\)).

Output format

Find the suitable substring.

 

SAMPLE INPUT
xyzxyzabcabc
SAMPLE OUTPUT
xyz
Explanation

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

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?