Longest Substring with Two Distinct Characters

Given a string, your task is to compute the longest substring that contains at most two distinct characters. In case there are multiple substrings that satisfy this property and have the same maximum length, return the one which appears first in the original string.

Note: The input string may be empty. The substring is defined as a contiguous sequence of characters from the original string.

Example:

• For input abcbbbbcccbdddadacb, the output is bcbbbbcccb.
• For input aaaaa, the output is aaaaa.
• For input abba, the output is abba.
• For input abcdef, the output is ab.

The solution should be implemented using a sliding window algorithm. More formally, if we denote the input string by \(s\) and the substring we are searching for by \(t\), then \(t\) is the longest substring such that \(t = s[i\ldots j]\) for some indices \(i\) and \(j\) (with \(i \leq j\)) and \(t\) contains at most two distinct characters. One common approach is to use two pointers to maintain the bounds of the current sliding window, and a hash map (or similar data structure) to count the occurrences of each character in the window.

The formal constraint on the number of distinct characters can be stated in LaTeX as:

$$\text{If } t \subseteq s \text{ then } |\{ c : c \in t \}| \leq 2.$$

inputFormat

The input consists of a single line containing a non-negative string \(s\). The string may be empty.

outputFormat

Output the longest substring of \(s\) that contains at most two distinct characters. If there are multiple such substrings with the maximum length, output the one that appears first.

## sample

abcbbbbcccbdddadacb

bcbbbbcccb