Problem

Submissions

Hints & solutions

Discuss

Longest Substring Without Repeating Characters

Moderate

0/80

Average time to solve is 20m

77 upvotes

Asked in companies

Problem statement

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

Suppose given input is "abacb", then the length of the longest substring without repeating characters will be 3 ("acb").

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

Each input contains a single line which contains the string 'S', Where 'S' denotes the input string containing english letters ( both UpperCase and LowerCase), digits, symbols, and spaces.

Output Format:

Print a single integer denoting the length of the longest substring without repeating characters.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

0 <= L <= 10^5     

Time limit: 1 sec

Sample Input 1:

xyxyz

Sample Output 1:

Explanation for Sample Output 1:

The substrings without repeating characters are "xy", "yx", "xyz", "yz", "z".
The longest substring out of these substrings is “xyz” of length 3.

Sample Input 2:

xxx

Sample Output 2:

Explanation for Sample Output 2:

The substrings without repeating characters is only "x" with length 1.

Hint 1

Hint 2

Hint 3

Hint 4

Check for all possible substrings and update the longest length accordingly.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute Force

In the brute force approach, we will use two nested loops. The outer loop is used to select the starting index of the substring and the inner loop is used to fix the ending index of the substring. After selecting the substring, we will use another loop (or a method) to check whether the substring contains all unique characters or not using a HashSet.

Time Complexity

O(L^3), where L is the length of the input string.

In the worst case, we will be selecting all substring by choosing two pointers i, j using two nested loops O(L^2) and for each selected substring we are checking whether it contains all unique characters or not in O(L). Thus, the Overall time complexity will be O(L^2 * L) i.e O(L^3).

Space Complexity

O(L), where L is the length of the input string.

Since we will be storing all the characters of the string in the set. Thus, the space complexity will be O(L).

(100% EXP penalty)

Longest Substring Without Repeating Characters

Console