Longest Substring Without Repeating Characters (opens in a new tab) Medium

Problem

Given a string s, find the length of the longest substring without repeating characters.

Example

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Summary

To solve this problem, we can use the sliding window technique, keeping track of the characters in the current window using a Map or Set. We will slide the window by incrementing the start and end pointers while making sure that there are no duplicate characters in the current window. We can keep track of the maximum length of the substring without repeating characters.

Solution

In TypeScript

function lengthOfLongestSubstring(s: string): number {
	let start = 0;
	let maxLength = 0;
	const charSet = new Set<string>();
 
	for (let end = 0; end < s.length; end++) {
		const char = s[end];
		while (charSet.has(char)) {
				charSet.delete(s[start]);
				start++;
		}
		charSet.add(char);
		maxLength = Math.max(maxLength, charSet.size);
	}
 
	return maxLength;
}

In Python

def lengthOfLongestSubstring(s: str) -> int:
	start = 0
	maxLength = 0
	charSet = set()
 
	for end in range(len(s)):
		char = s[end]
		while char in charSet:
			charSet.remove(s[start])
			start += 1
		charSet.add(char)
		maxLength = max(maxLength, len(charSet))
 
	return maxLength

Step-by-step explanation

1. Initialize the start pointer to 0, maxLength to 0, and create a new Set called charSet.

let start = 0;
let maxLength = 0;
const charSet = new Set<string>();

2. Loop through the string with a for loop, using the end index as the loop variable.

for (let end = 0; end < s.length; end++) {
	// ...
}

3. Get the character at the current end index.

const char = s[end];

4. Check if the character already exists in the charSet. If it does, we have a repeating character, and we need to remove the character at the start pointer from the charSet. Then, increment the start pointer. Keep doing this in a while loop until the current character is not in the charSet.

while (charSet.has(char)) {
		charSet.delete(s[start]);
		start++;
}

5. After the while loop, add the current character to the charSet.

charSet.add(char);

6. Update the maxLength with the maximum value between the current maxLength and the size of the charSet. Since the charSet contains all unique characters in the current window, its size represents the length of the substring without repeating characters.

maxLength = Math.max(maxLength, charSet.size);

7. Return the maxLength, which represents the length of the longest substring without repeating characters.

return maxLength;

The solution uses a sliding window approach with a Set to track the unique characters in the current window. By updating the start pointer when a repeating character is found, the window slides through the string, making sure it always contains a substring without repeating characters. The maximum length of such substring is stored in the maxLength variable.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string. We use a single for loop to iterate through the string and slide the window, adjusting the start pointer and end index accordingly. The inner while loop is used to update the start pointer when a repeating character is found. Since each character is visited at most twice (once by the outer loop and once by the inner loop), the overall time complexity remains O(n).

Space Complexity

The space complexity of this solution is O(min(n, m)), where n is the length of the input string, and m is the size of the character set. In the worst case, we will have to store all unique characters of the string in the Set. However, if the size of the character set is smaller than the length of the string, the space complexity will be limited by the size of the character set.