Finding the longest substring without repeating characters in a given string is a common problem in computer science. This problem can appear in many different contexts, such as finding the most efficient way to compress a string, or finding the maximum number of characters that can be used in a password. The solution to this problem is to use a sliding window approach, where a window “slides” over the given string and we keep track of the longest substring without repeating characters that is seen so far. In this article, we will discuss an efficient algorithm for solving this problem and provide an implementation in the programming language of your choice.
Problem Statement
From Leetcode:
Given a string s, find the length of the longest
substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Solving Leetcode 3
To approach this problem, we can use a sliding window approach. This involves maintaining a window of characters as we iterate over the given string. As we iterate through the string, we can check if the current character is already present in the window. If it is, then we can move the left side of the window to the right, so that the current character is no longer in the window. If the character is not present, then we can extend the window by adding the current character to the right side. In this way, we can keep track of the longest substring without repeating characters that is seen so far.
Below is a diagram showing how the sliding window algorithm works. As we iterate through the string, we can maintain a window of characters (shown in green). When we encounter a character that is already in the window, we move the left side of the window to the right, so that the current character is no longer in the window. If the character is not present, then we can extend the window by adding the current character to the right side.
Here is the code in Python:
def lengthOfLongestSubstring(s: str) -> int:
# Set initial values for the sliding window and maximum length.
window = set()
max_length = 0
# Iterate through the string, one character at a time.
for c in s:
# If the current character is in the set, remove characters
# from the start of the window until the set no longer
# contains the current character.
while c in window:
window.remove(s[0])
s = s[1:]
# Add the current character to the set and update the
# maximum length of the non-repeating substring seen so far.
window.add(c)
max_length = max(max_length, len(window))
# Return the maximum length of the non-repeating substring.
return max_length
This code uses a sliding window approach to find the longest non-repeating substring in the input string. It iterates through the string one character at a time, using a set to keep track of the characters in the current window. If the current character is in the set, the code removes characters from the start of the window until the set no longer contains the current character. Then, it adds the current character to the set and updates the maximum length of the non-repeating substring seen so far. At the end, it returns the maximum length.
The comments in the code explain the steps involved in the algorithm and can be used to visualize the flowchart of the solution. For example, the first block of comments explains the initial setup of the variables, while the second block of comments explains the iteration through the string and the steps involved in the sliding window algorithm. The third block of comments explains how the maximum length of the non-repeating substring is updated, and the final block of comments explains the return statement. By reading through the comments and following the code, you can see how the algorithm works and how it solves the problem.
Here’s an example of how the solution could be implemented in JavaScript:
function lengthOfLongestSubstring(s) {
// Set initial values for the sliding window and maximum length.
let window = new Set();
let maxLength = 0;
// Iterate through the string, one character at a time.
for (let c of s) {
// If the current character is in the set, remove characters
// from the start of the window until the set no longer
// contains the current character.
while (window.has(c)) {
window.delete(s[0]);
s = s.substring(1);
}
// Add the current character to the set and update the
// maximum length of the non-repeating substring seen so far.
window.add(c);
maxLength = Math.max(maxLength, window.size);
}
// Return the maximum length of the non-repeating substring.
return maxLength;
}
This code uses a sliding window approach to find the longest non-repeating substring in the input string. It iterates through the string one character at a time, using a set to keep track of the characters in the current window. If the current character is in the set, the code removes characters from the start of the window until the set no longer contains the current character. Then, it adds the current character to the set and updates the maximum length of the non-repeating substring seen so far. At the end, it returns the maximum length.
Diagram
Time & Space Complexity
The time complexity of the solution to the Leetcode 3. Longest Substring Without Repeating Characters problem is O(n), where n is the length of the input string. This is because the algorithm iterates through the input string one character at a time, so the time complexity is directly proportional to the length of the string.
The space complexity of the solution is also O(n), because the set used to keep track of the current, non-repeating substring can have a maximum size of n. This is because, in the worst case, the entire input string could be a non-repeating substring, in which case the set would need to store all n characters from the string. Therefore, the space complexity is also directly proportional to the length of the input string.
This was one of the more common questions in the field of computer science. It can be solved using a sliding window algorithm, which involves iterating through the input string and keeping track of the current, non-repeating substring using a set. By constantly updating the set and the maximum length of the non-repeating substring seen so far, it is possible to find the longest non-repeating substring in the input string. This solution is both efficient and effective, making it a popular choice for solving this type of problem.
See Similar Problems.
- Integer to Roman
- Group Anagrams