Longest Substring Without Repeating Characters

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
147 upvotes
Asked in companies
FreshworksQualcommAdobe

Problem statement

Given a string input of length n, find the length of the longest substring without repeating characters i.e return a substring that does not have any repeating characters.

Substring is the continuous sub-part of the string formed by removing zero or more characters from both ends.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
 The first and the only line consists of a string of length n containing lowercase alphabets.
Output format: 
 You need to print the length of the longest unique characters substring.
Constraints: 
 1<= n <=10^5

Time Limit: 1 sec
Sample Input 1:
 abcabcbb
Sample Output1:
 3
Explanation For Sample Input 1:
Substring "abc" has no repeating character with the length of 3.
Sample Input 2:
 aaaa
Sample Output 2:
1
Hint

Think of creating all of the substrings.

Approaches (2)
All Substring Approach
  • Create all the substrings of the string.
  • For every substring, check if it consists of unique characters.
  • To check if the substring has duplicate characters, we will use a HashSet. We will iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If it does, the substring doesn't contain unique characters and we can break the loop at that point. If the entire loop is executed without breaking, then the substring contains unique characters
  • If the length of the current substring with unique characters is greater than the maximum length of the substring we've found (initially 0), then we'll update it.
  • Return the maximum length of the substring with unique characters
Time Complexity

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

 

We would be creating every substring, which takes N^2 time, and for checking whether it consists of unique characters, it will take N time.

Space Complexity

O(N), where N is the length of the string. 

 

Since we have used set for checking duplication in strings.

Code Solution
(100% EXP penalty)
Longest Substring Without Repeating Characters
Full screen
Console