How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Longest Substring Without Repeating Characters

MediumAcceptance: 33.8%

Hash Table String Sliding Window

Problem Statement

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

Constraints:

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces

Input Format:

A string s

Output Format:

The length of the longest substring without repeating characters

Examples:

Example 1:

Input:

s = "abcabcbb"

Output:

Explanation:

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

Example 2:

Input:

s = "bbbbb"

Output:

Explanation:

The answer is "b", with the length of 1.

Example 3:

Input:

s = "pwwkew"

Output:

Explanation:

The answer is "wke", with the length of 3. Notice that the answer must be a substring, not a subsequence.

Example 4:

Input:

s = ""

Output:

Explanation:

An empty string has a length of 0.

Solutions

Sliding Window with Hash Map

Time: O(n)

Space: O(min(m, n)) where m is the size of the character set

Use a sliding window and a hash map to track character positions.

Sliding Window with Set

Time: O(n)

Space: O(min(m, n)) where m is the size of the character set

Use a sliding window and a set to track characters in the current window.

Algorithm Walkthrough

Example input:

Step-by-step execution:

s = "abcabcbb", charMap = {}, maxLength = 0, start = 0
end=0, char='a': charMap = {'a': 0}, maxLength = 1
end=1, char='b': charMap = {'a': 0, 'b': 1}, maxLength = 2
end=2, char='c': charMap = {'a': 0, 'b': 1, 'c': 2}, maxLength = 3
end=3, char='a': found in map at 0, start = 0+1 = 1, charMap = {'a': 3, 'b': 1, 'c': 2}, maxLength = 3
end=4, char='b': found in map at 1, start = 1+1 = 2, charMap = {'a': 3, 'b': 4, 'c': 2}, maxLength = 3
end=5, char='c': found in map at 2, start = 2+1 = 3, charMap = {'a': 3, 'b': 4, 'c': 5}, maxLength = 3
end=6, char='b': found in map at 4, start = 4+1 = 5, charMap = {'a': 3, 'b': 6, 'c': 5}, maxLength = 3
end=7, char='b': found in map at 6, start = 6+1 = 7, charMap = {'a': 3, 'b': 7, 'c': 5}, maxLength = 3
Return maxLength = 3

Hints

Hint 1

Use a sliding window approach with a hash map to track characters.

Hint 2

When you find a repeated character, update the start of the window.

Hint 3

Keep track of the maximum length seen so far.

Video Tutorial

Longest Substring Without Repeating Characters - Sliding Window

YouTube•Learn the Longest Substring Without Repeating Characters solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the sliding window as it moves through the string, expanding and contracting to find the longest substring without repeating characters.

Key visualization elements:

current character
window range
character set

Asked By

Amazon Microsoft Facebook Google Apple Bloomberg

Implementation Notes

This problem is a classic application of the sliding window technique. It's important to understand that the problem asks for a substring (consecutive characters) rather than a subsequence (characters that might not be consecutive).