Longest Substring Without Duplication

Category: Strings

Difficulty: Hard

Description

Write a function that takes in a string and returns its longest substring without duplicate characters.

You can assume that there will only be one longest substring without duplication.

Sample Input

string = "clementisacap"

Sample Output

"mentisac"

Optimal Space & Time Complexity

O(n) time | O(min(n, a)) space - where n is the length of the input string and a is the length of the character alphabet represented in the input string