Katkat
Back

Find longest substring without repeating characters

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window technique combined with a hash map to efficiently find a maximal subarray meeting a specific constraint.

Problem Statement

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

Function Signature

def lengthOfLongestSubstring(s: str) -> int:

Constraints

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

Examples

Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with a length of 3.

Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with a length of 1.

Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with a length of 3. Note that the answer must be a substring, not a subsequence.

Considerations

  • Your solution should aim for O(n) time complexity, where n is the length of the string.
  • Consider how to store the last seen index of each character to "jump" the start of your window forward when a duplicate is found.

Hints

Hint 1

Use two pointers to define a sliding window representing the current substring without duplicates.

Hint 2

Maintain a hash map or an array to store the most recent index where each character appeared.

Hint 3

When you encounter a character already in your map, move the start of the window to the position after the last occurrence of that character, but only if that position is to the right of your current start pointer.

Follow-up questions

  • How would you modify the solution if the input string contained Unicode characters rather than standard ASCII?
  • Can you explain why the time complexity is O(n) even though there is a nested movement of pointers?
  • How would you return the actual substring itself instead of just the maximum length?