Longest Substring Without Repeating Characters
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").

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

Question

Longest Substring Without Repeating Characters

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").

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

Follow Up:

Can you solve this problem in O(L) time and space complexity?

Accepted Answer

The brute force approach would be to consider all substrings one by one and check for each substring whether it contains all unique characters or not. There will be n*(n+1)/2 substrings. Time complexity of this solution would be O(n^3).

For an efficient solution, a hashmap can be used. Maintain a hashmap which stores the characters in string as keys and their indexes(positions) as values, and keep two pointers which define the max substring. move the right pointer to traverse through the string, and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Keep updating the max length Non-Repeating Character Substring seen so far.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n^3)Explanation:

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).

Accepted Answer

Optimized Brute Force

In this 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.

Inside the outer loop, we will initialize a HashSet to store the unique characters. Now we will keep adding the characters to this set using the inner loop. Before adding each character if the character is already present in the set this means that from ith index to current jth index this character is repeated. So we will not consider this substring and any other substring starting from the ith index and ending at j or after, break from the inner loop. Otherwise, we will update the longest length and add the character to the set.

Space Complexity: O(1)Explanation:

O(D), where D is the maximum number of distinct characters.

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

Time Complexity: O(n)Explanation:

O(L*D), where L is the length of the input string and D is the maximum number of distinct characters.

In the worst case, we will be only selecting all substring by choosing two pointers i, j using two nested loops and whenever we encounter a repeated character we will break from the inner loop. Thus the overall complexity will be O(L*D).

Accepted Answer

Binary Search

In this approach, we will use a binary search to select the length of the substring. The smallest value possible will be 1 as all the characters are unique substrings themselves and the maximum value for binary search will be ‘L’ as there is no substring wth length more than L in the given string where L is the length of the given input string.

Now doing the binary search on the range start = 1 to end = L. We will check for ‘mid’(start + end)/2 length, whether there is any substring with length equals to ‘mid’ with unique characters or not. If such substring exists we will update the answer and move to right side ie start = mid + 1. Otherwise, we will check on the left side i.e end = mid - 1.

Now to check whether a substring of length ‘mid’ exists on or not we will iterate on the whole string. Given below is the algorithm to check this.

Steps Required to calculate the length:

Boolean isDistinctSubstringExists(input, mid):

Initialize the map to store frequencies.
For each character in the input, i.e i = 0 to L - 1, where L is the length of the input string.
- Increment the current character’s frequency in the map.
- If i >= mid, decrease the frequency of (i - mid)th character. If it is zero remove it from the map.
- If the map current size equals to the mid-value, return true.
No substring of length equals to mid found, return false.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

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

In the worst case, we will be selecting length using binary search O(log L) and for all such lengths iterating the string in O(L) to check unique substring existence. Thus the overall time complexity will be O(L*log(L)).

Accepted Answer

Sliding Window Approach

We will keep a window that will keep a range of unique characters where the range is defined by start and end indices. Initially, both ‘start' and ‘end’ equal to zero denoting that we have only one character in the current window i.e the character at 0th index. Along with this, we will also keep a HashMap/ Unordered Map to store the last occurrence of the characters. Now we will keep incrementing the ‘end’ to iterate on each character of the string.

If the current character at the ‘end’ index is not present in the window we will simply update the ‘start' to the maximum index possible index of ‘start’ or the last occurrence of the current character. Then we update the ‘maxLen’ and it gets updated if the range ('end' - ‘start’ - 1) is greater than ‘maxLen’. Then store the current index in the Map/HashMap as the current index will be the last occurrence of the character till current index iterated. Also, increment the ‘end’ by 1. Finally, Return ‘maxLen’.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(n)Explanation:

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

Since we will be only iterating the given input string once and Thus the time complexity will be O(L).

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

Example:

Input Format:

Output Format:

Note:

Constraints:

Follow Up:

Top Housing.com Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Housing.com Software Developer