Last Updated: 17 Jul, 2020
Longest Substring Without Repeating Characters
Moderate
Asked in companies
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.
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
Approaches
- 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
- Take two pointers (start and end) initially both at 0th index and a set which will be storing the characters between start and end index.
- While both pointers are less than the length of the string:
- Check if end pointer character is present in the set or not
- If it is not present, then move the end pointer to the right and include the character in the set. The length of the substring will be “end - start + 1”. If this is greater than the maximum length of substring with unique characters (initially 0), update the maximum length
- Else if it is present, remove the character at the start pointer from the set and move the start pointer to the right.
- Return the maximum length of the substring with unique characters