An environmental monitoring station writes every reading from its field sensors into one continuous log string s. Each character is a letter that names a sensor: an uppercase letter marks a calibrated reading from that sensor, and the matching lowercase letter marks a raw reading from the very same sensor (so 'T' and 't' both refer to sensor T).
A contiguous fragment of the log is called dual-verified if, for every sensor whose letter (in either case) appears anywhere inside the fragment, the fragment also contains at least one calibrated reading and at least one raw reading for that sensor.
Find the longest dual-verified fragment of s. If several fragments share the maximum length, output the one that begins earliest in the log. If no non-empty fragment is dual-verified, output an empty line.
A single line containing the log string s.
A single line containing the longest dual-verified fragment of s (an empty line if none exists).
s consists only of uppercase and lowercase English letters ('a'-'z', 'A'-'Z').Example 1
Input
QqRrSsT
Expected
QqRrSs
Explanation
Every letter except T has both cases present (Q/q, R/r, S/s). T appears only in uppercase with no lowercase t anywhere in the log, so no fragment containing T can ever be dual-verified. Excluding it leaves "QqRrSs", which is fully dual-verified and is the longest possible fragment.
Example 2
Input
Zebra
Expected
(empty)Explanation
Every letter in "Zebra" (Z, e, b, r, a) appears in only one case in the whole string, so no letter ever has both its calibrated and raw reading present together. No non-empty fragment can be dual-verified, so the output is an empty line.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →