Question

How to find the longest substring without repeating characters in Python

Answer 1

def longest_unique_substring_ascii(s: str) -> str:
    """
    Finds the longest substring without repeating characters.
    This version keeps a presence table and shrinks the window
    by clearing characters until the duplicate is removed.

    Time complexity: O(n)
    """
    seen = [False] * 256  # ASCII presence table

    left = 0
    right = 0
    best_left = 0
    best_right = 0

    n = len(s)

    while right < n:
        c = ord(s[right])

        if seen[c]:
            # Shrink window until we remove the duplicate
            while s[left] != s[right]:
                seen[ord(s[left])] = False
                left += 1
            left += 1  # skip the duplicate itself
        else:
            seen[c] = True

            if right - left > best_right - best_left:
                best_left = left
                best_right = right

        right += 1

    return s[best_left:best_right + 1]


if __name__ == "__main__":
    s = "xwwwqfwwxqwyq"
    result = longest_unique_substring_ascii(s)

    print("Input:", s)
    print("Longest substring without repeating characters:", result)



"""
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

"""

 

70+ SQL courses for beginners and professionals

Answer 2

def longest_substring(s: str) -> str:
    start = 0
    max_length = 0
    char_index_map = {}
    longest_substr = ""

    # Iterate through the string
    for end in range(len(s)):
        if s[end] in char_index_map and char_index_map[s[end]] >= start:
            # Move the start pointer to avoid duplicates
            start = char_index_map[s[end]] + 1
        
        # Update the character's latest index
        char_index_map[s[end]] = end
        
        # Check if the current substring is the longest
        current_length = end - start + 1
        if current_length > max_length:
            max_length = current_length
            longest_substr = s[start:end + 1]
    
    return longest_substr


print(longest_substring("abcabcbb"))  # Output: "abc"
print(longest_substring("bbbbb"))    # Output: "b"
print(longest_substring("xwwwqfwwxqwyq"))   # Output: "xqwy"



'''
run:

abc
b
xqwy

'''

 

70+ SQL courses for beginners and professionals

Answer 3

def longest_unique_substring(s: str) -> str:
    """
    Finds the longest substring without repeating characters.
    Uses a sliding window and a table of last-seen indexes.

    - last_seen[c] stores the most recent index of character c.
    - left/right define the current window.
    - When a duplicate appears inside the window, move left forward.

    Time complexity: O(n)
    """
    last_seen = [-1] * 256  # ASCII table

    left = 0
    best_start = 0
    best_length = 0

    for right, ch in enumerate(s):
        c = ord(ch)

        # If character was seen inside the current window, move left
        if last_seen[c] >= left:
            left = last_seen[c] + 1

        # Update last-seen index
        last_seen[c] = right

        # Check if this window is the best so far
        window_length = right - left + 1
        if window_length > best_length:
            best_length = window_length
            best_start = left

    return s[best_start:best_start + best_length]


if __name__ == "__main__":
    s = "xwwwqfwwxqwyq"
    result = longest_unique_substring(s)

    print("Input:", s)
    print("Longest substring without repeating characters:", result)



"""
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

"""

 

70+ SQL courses for beginners and professionals