Longest Unique Substring

Given a string s, find the longest substring that contains no repeated characters. If there are multiple substrings with the same maximum length, return the one that appears first in s.

The task is to implement an algorithm that efficiently computes this substring. One common approach is to use a sliding window technique with a hash map (or similar data structure) to track the characters and their most recent positions.

Mathematical Explanation: Let s be a string of length n. We maintain two pointers start and end (with 0 ≤ start ≤ end < n) to represent the current window of unique characters. For each character s[end]:

\[ \text{if } s[end] \text{ is in the window, update } start = \max(start, \text{last_index}[s[end]] + 1), \]

Then update the last seen index of s[end] to end and check if the current window size (end - start + 1) is larger than the current maximum. Finally, output the substring from start to end.

inputFormat

The input consists of a single line containing the string s. The string may contain letters, digits or symbols. Read the input from standard input (stdin).

outputFormat

Output the longest substring of s without repeating characters to standard output (stdout).## sample

abcabcbb

abc