Longest Substring with At Most Two Distinct Characters

Given a string s, find the longest substring that contains at most two distinct characters.

More formally, you are given a string s of length n and you need to find a substring s[i...j] (with 0 ≤ i ≤ j < n) such that the number of distinct characters in the substring is at most 2 and its length is as long as possible. If there are multiple answers, return the substring that appears first (i.e. the one with the smallest starting index).

You can use the sliding window technique. The problem can be formally expressed as:

Find the maximum length L such that there exists indices i and j with
\(j - i + 1 = L\) and \(\left|\{s[i], s[i+1], \dots, s[j]\}\right| \le 2\).

Example:

• Input: eceba → Output: ece
• Input: ccaabbb → Output: aabbb

inputFormat

The input consists of a single line containing a non-empty string s.

The string is read from standard input (stdin).

outputFormat

Output the longest substring of s that contains at most two distinct characters. The output should be written to standard output (stdout).

## sample

eceba

ece