To solve this problem, we need to find the length of the longest substring without repeating characters in a given string. The optimal approach involves using a sliding window technique combined with a hash map to efficiently track the last occurrence of each character, ensuring an O(n) time complexity.

Approach

1. Sliding Window: We use two pointers (left and right) to represent the current window of characters being considered.
2. Hash Map: A hash map (dictionary) stores the last index of each character encountered. This helps in quickly determining if a character is already in the current window and adjusting the window's left boundary if necessary.
3. Adjust Window: For each character at position right:
   • If the character is already in the hash map and its last index is within the current window (>= left), move the left pointer to the right of the last occurrence of this character.
   • Update the hash map with the current index of the character.
   • Calculate the length of the current window and update the maximum length if the current window is longer.

Solution Code

def lengthOfLongestSubstring(s):
    char_map = {}
    max_len = 0
    left = 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

• Initialization: char_map keeps track of the last index of each character. max_len stores the length of the longest substring found. left is the start of the current window.
• Iterate with Right Pointer: For each character at right, check if it's in the map and within the current window. If so, adjust the left pointer to exclude duplicates.
• Update Map: Store the current index of the character in the map.
• Update Max Length: Compute the current window length and update max_len if it's larger than the previous maximum.

This approach efficiently processes each character exactly once, making it optimal for large strings. The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII).

Examples:

• Input: "abcabcbb" → Output: 3 (substring "abc")
• Input: "bbbbb" → Output:1 (substring "b")
• Input: "pwwkew" → Output:3 (substring "wke" or "kew")

This solution handles all edge cases, including empty strings (output:0) and single characters (output:1). It's a robust and efficient way to solve the problem.

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