Table of Contents
The problem “Longest Substring Without Repeating Characters” is a classic algorithmic problem in computer science. Given a string, the task is to find the length of the longest substring within the string that does not contain any repeated characters.
For example, consider the input string “abcabcbb”. The longest substring without repeating characters is “abc”, which has a length of 3. Another example is the input string “pwwkew”. The longest substring without repeating characters is “wke”, which has a length of 3.
This problem requires finding a substring within a given string that satisfies certain conditions, which is a common problem in computer science. The solution involves using various algorithms such as sliding window, hash table, or two pointers, to efficiently search for the longest substring without repeating characters.
There are multiple approaches to solve the “Longest Substring Without Repeating Characters”.
Approach 1: Sliding Window with Hash Set
This approach uses a sliding window technique to keep track of the current substring without repeating characters. We use a hash set to keep track of the characters in the current window. When we encounter a repeating character, we move the left pointer of the window to the right until the repeating character is no longer in the window.
Here’s the pseudocode:
function lengthOfLongestSubstring(s: string) -> int:
n = length(s)
i = 0
j = 0
max_len = 0
char_set = set()
while i < n and j < n:
if s[j] not in char_set:
char_set.add(s[j])
j += 1
max_len = max(max_len, j - i)
else:
char_set.remove(s[i])
i += 1
return max_len
Time Complexity: O(n)
Space Complexity: O(min(m, n)), where m is the size of the character set
Approach 2: Sliding Window with Hash Map
This approach is similar to Approach 1 but uses a hash map instead of a hash set to keep track of the characters in the current window. The hash map stores the index of the last occurrence of each character in the current window. When we encounter a repeating character, we move the left pointer of the window to the right of the last occurrence of the repeating character.
Here’s the pseudocode:
function lengthOfLongestSubstring(s: string) -> int:
n = length(s)
i = 0
j = 0
max_len = 0
char_map = {}
while j < n:
if s[j] in char_map:
i = max(char_map[s[j]], i)
max_len = max(max_len, j - i + 1)
char_map[s[j]] = j + 1
j += 1
return max_len
Time Complexity: O(n)
Space Complexity: O(min(m, n)), where m is the size of the character set
Approach 3: Brute Force
This approach checks every possible substring for the presence of repeating characters. We maintain a set of characters for each substring and check whether the length of the set is equal to the length of the substring. We repeat this for all possible substrings and keep track of the maximum length found.
Here’s the pseudocode:
function lengthOfLongestSubstring(s: string) -> int:
n = length(s)
max_len = 0
for i in range(n):
char_set = set()
j = i
while j < n and s[j] not in char_set:
char_set.add(s[j])
j += 1
max_len = max(max_len, j - i)
return max_len
Time Complexity: O(n^3)
Space Complexity: O(min(m, n)), where m is the size of the character set
As we can see, Approach 1 and 2 are much more efficient than Approach 3.
Which solution is efficient and why?
Approach 3 is a brute force approach that checks every possible substring for the presence of repeating characters. This approach has a time complexity of O(n^3), where n is the length of the input string, because it considers all possible substrings and then checks each one for repeating characters using a hash set.
Approach 3 is not as efficient as Approach 1 or Approach 2 because it considers all possible substrings, which is a much larger set of substrings than the set of substrings considered by the sliding window approaches. As a result, Approach 3 can potentially check many substrings that are not candidates for the longest substring without repeating characters.
In contrast, both Approach 1 and Approach 2 use a sliding window technique to iteratively consider substrings that are contiguous and have not been seen before. This is a much more efficient approach, as it avoids checking many substrings that are not candidates for the longest substring without repeating characters.
Therefore, Approach 3 is not as good as Approach 1 or Approach 2 because it is less efficient and more general than the other approaches, which use a sliding window technique to search for the longest substring without repeating characters.
Approach 1 and Approach 2 are both efficient solutions to the “Longest Substring Without Repeating Characters” problem, with a time complexity of O(n) and a space complexity of O(min(m, n)), where n is the length of the input string and m is the size of the character set.
Approach 1 uses a hash set to keep track of the characters in the current window, while Approach 2 uses a hash map to store the index of the last occurrence of each character in the current window. Both approaches use a sliding window technique to search for the longest substring without repeating characters.
Between these two approaches, Approach 2 is slightly more efficient because it can avoid unnecessary iterations of the left pointer by directly setting it to the index of the last occurrence of the repeating character. In contrast, Approach 1 iterates the left pointer one by one until the repeating character is no longer in the window.
Overall, Approach 2 is the better solution because it is more efficient and also more generalizable to other similar problems that require tracking the last occurrence of a certain element in a sliding window.
Longest Substring Without Repeating Characters: Python Solution
def length_of_longest_substring(s: str) -> int:
n = len(s)
i = 0
j = 0
max_len = 0
char_map = {}
while j < n:
if s[j] in char_map and char_map[s[j]] >= i:
i = char_map[s[j]] + 1
max_len = max(max_len, j - i + 1)
char_map[s[j]] = j
j += 1
return max_len
In this implementation, we initialize the left pointer i and right pointer j to 0, and the maximum length max_len to 0. We also initialize an empty hash map char_map to store the last occurrence of each character in the current window.
We then use a while loop to iterate through the string s with the right pointer j. If the character at s[j] is already in the hash map and its index is greater than or equal to the left pointer i, we update i to the index of the last occurrence of the character plus one to move the left pointer to the right of the last occurrence.
We then update max_len with the maximum length of the current substring without repeating characters and update the hash map with the index of the current character.
Longest Substring Without Repeating Characters: Ruby Solution
def length_of_longest_substring(s)
n = s.length
i = 0
j = 0
max_len = 0
char_map = {}
while j < n do
if char_map.has_key?(s[j]) && char_map[s[j]] >= i
i = char_map[s[j]] + 1
end
max_len = [max_len, j - i + 1].max
char_map[s[j]] = j
j += 1
end
return max_len
end
In this implementation, we initialize the left pointer i and right pointer j to 0, the maximum length max_len to 0, and the hash map char_map to store the last occurrence of each character in the current window.
We then use a while loop to iterate through the string s with the right pointer j. If the character at s[j] is already in the hash map and its index is greater than or equal to the left pointer i, we update i to the index of the last occurrence of the character plus one to move the left pointer to the right of the last occurrence.
We then update max_len with the maximum length of the current substring without repeating characters and update the hash map with the index of the current character.
Longest Substring Without Repeating Characters: JavaScript Solution
function lengthOfLongestSubstring(s) {
const n = s.length;
let i = 0, j = 0, maxLen = 0;
const charMap = new Map();
while (j < n) {
if (charMap.has(s[j]) && charMap.get(s[j]) >= i) {
i = charMap.get(s[j]) + 1;
}
maxLen = Math.max(maxLen, j - i + 1);
charMap.set(s[j], j);
j++;
}
return maxLen;
}
In this implementation, we initialize the left pointer i and right pointer j to 0, the maximum length maxLen to 0, and the charMap to store the last occurrence of each character in the current window using a JavaScript Map.
We then use a while loop to iterate through the string s with the right pointer j. If the character at s[j] is already in the charMap and its index is greater than or equal to the left pointer i, we update i to the index of the last occurrence of the character plus one to move the left pointer to the right of the last occurrence.
We then update maxLen with the maximum length of the current substring without repeating characters and update the charMap with the index of the current character using the set method.
Longest Substring Without Repeating Characters: Java Solution
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int i = 0, j = 0, maxLen = 0;
Map<Character, Integer> charMap = new HashMap<>();
while (j < n) {
if (charMap.containsKey(s.charAt(j)) && charMap.get(s.charAt(j)) >= i) {
i = charMap.get(s.charAt(j)) + 1;
}
maxLen = Math.max(maxLen, j - i + 1);
charMap.put(s.charAt(j), j);
j++;
}
return maxLen;
}
In this implementation, we initialize the left pointer i and right pointer j to 0, the maximum length maxLen to 0, and the charMap to store the last occurrence of each character in the current window using a Java HashMap.
We then use a while loop to iterate through the string s with the right pointer j. If the character at s.charAt(j) is already in the charMap and its index is greater than or equal to the left pointer i, we update i to the index of the last occurrence of the character plus one to move the left pointer to the right of the last occurrence.
We then update maxLen with the maximum length of the current substring without repeating characters and update the charMap with the index of the current character using the put method.
