largest natural number - Amex Data engineering Role Online Assessmnet IIT Roorkee

Problem Preview

"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)."