There is a string S made only of non-zero digits (1 - 9). Among all contiguous fragments of S that contain at most two distinct digits, find the one that represents the largest natural number.

Write a function:

string solution(string &S);

that, given string S, returns a fragment of S that contains at most two distinct digits and represents the largest possible natural number. If multiple fragments represent the same largest number, return any of them.

Examples:

Given S = "32581", the function should return "81".

Given S = "91222", the function should return "1222".

Given S = "121231221", the function should return "1221".

Write an efficient algorithm for the following assumptions:

the length of string S is within the range [1..200,000];

string S consists only of non-zero digits (1 - 9).