Katkat
Back

Longest Substring Without Repeating Characters

AntraSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement an efficient sliding window technique using a hash map to track character indices and maintain a valid substring 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 the length of 3.

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

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

Considerations

  • How do you handle cases with empty strings?
  • What is the time and space complexity of your solution?

Hints

Hint 1

Consider using two pointers to define a 'window' of characters that satisfy the unique constraint.

Hint 2

Use a hash map or an array to store the last seen index of each character to quickly jump the start pointer when a duplicate is found.

Hint 3

Ensure the start pointer only moves forward and never backward, even if a character was seen previously.

Follow-up questions

  • How would your approach change if the input was a stream of characters rather than a static string?
  • Can you optimize the space complexity if you know the character set is limited (e.g., only ASCII)?
  • What is the time complexity of your solution, and can it be achieved in O(n) time?