Longest Unique Substring
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

Question

Longest Unique Substring

 The first and the only line consists of a string of length n containing lowercase alphabets.

 You need to print the length of the longest unique characters substring.

 1<= n <=10^5

Time Limit: 1 sec

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

Since we have used set for checking duplication in strings.

Time Complexity: O(n^3)Explanation:

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.

Accepted Answer

Sliding Window Approach

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

Space Complexity: OtherExplanation:

O(k), where k is the number of unique characters in the string.

Since we are storing K elements.

Time Complexity: O(n)Explanation:

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

As we would be considering one character at a time.

Top Freshworks Lead Software Engineer interview questions & answers