To solve this problem, we need to find the length of the longest substring without repeating characters. The optimal approach involves using a sliding window technique combined with a hash map to efficiently track the last occurrence of each character, allowing us to adjust the window size dynamically.

Approach

The key idea is to maintain a sliding window defined by two pointers (left and right). The right pointer expands the window by moving to the right, while the left pointer contracts the window when a duplicate character is encountered. A hash map is used to store the last index of each character, enabling us to jump the left pointer directly to the position after the last occurrence of the duplicate character, thus optimizing the window adjustment.

1. Initialization:

   • left pointer starts at 0.
   • max_len keeps track of the length of the longest substring found.
   • char_map stores the last index of each character in the string.

2. Expand the Window:

   • Iterate over the string with the right pointer.
   • If the current character is already in char_map and its last occurrence is within the current window (i.e., >= left), move the left pointer to the position after the last occurrence of the duplicate character.
   • Update the last index of the current character in char_map.
   • Calculate the current window length and update max_len if the current window is longer.

3. Return Result:

   • The value of max_len after processing all characters gives the length of the longest substring without repeating characters.

Solution Code

def lengthOfLongestSubstring(s):
    char_map = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        char = s[right]
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1
        char_map[char] = right
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
    return max_len

Explanation

• Sliding Window: The window is defined by left and right pointers. The window expands as right moves right, and contracts when a duplicate is found.
• Hash Map: The hash map (char_map) stores the last index of each character, allowing us to quickly adjust the left pointer to avoid duplicates.
• Efficiency: The algorithm runs in O(n) time complexity, where n is the length of the string, since each character is processed at most twice (once by right and once by left). The space complexity is O(min(m, n)), where m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII), as the hash map only stores unique characters in the current window.

This approach efficiently finds the longest substring without repeating characters, making it suitable for large input sizes. The solution handles all edge cases, including empty strings, single-character strings, and strings with all unique characters.

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。