{x}
blog image

Longest Substring Without Repeating Characters

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

 

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, "pwke" is a subsequence and not a substring.

 

Constraints:

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

Solution Explanation: Longest Substring Without Repeating Characters

This problem asks for the length of the longest substring without repeating characters. The optimal solution utilizes the sliding window technique along with a hash table (or array) to efficiently track character frequencies.

Approach:

  1. Initialization:

    • cnt: A hash table (or an array of size 128 to accommodate ASCII characters) to store the frequency of each character encountered in the current window. We use Counter in Python, and Map in TypeScript and JavaScript for efficient counting. Other languages use arrays for simplicity and direct indexing.
    • ans: A variable to keep track of the maximum length of the substring found so far, initialized to 0.
    • l: A left pointer indicating the start of the sliding window, initialized to 0.
    • r: A right pointer indicating the end of the sliding window, initialized to 0.

  2. Sliding Window Iteration:

    • The outer loop iterates through the input string s using the right pointer r.
    • Character Frequency Update: For each character c at index r, we increment its count in cnt.
    • Window Adjustment: If the count of c becomes greater than 1 (meaning a repeating character is found), it indicates the window contains a repeating character. We then move the left pointer l to the right, decrementing the counts of characters encountered until the count of c is reduced to 1, ensuring the window again contains no repeating characters.
    • Answer Update: After each adjustment, ans is updated to the maximum of ans and the current window size (r - l + 1).

  3. Return Value:

    • Finally, the function returns ans, which represents the length of the longest substring without repeating characters.

Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice (once by the right pointer and at most once by the left pointer).

Space Complexity: O(1). The space used by cnt is constant because it is bounded by the number of unique characters (128 for ASCII). In cases with extended character sets, it would be O(k), where k is the size of the character set. However, in this case, the input constraints limit characters to the basic ASCII set.

Code Examples (as provided previously):

The code examples in Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#, PHP, Swift, and Kotlin demonstrate this algorithm. Each language uses slightly different syntax and data structures for implementing the hash table and sliding window, but the core logic remains the same. The provided examples are concise and efficient.