Longest Substring Without Repeating Characters - Python Solution

1. Introduction

"Longest Substring Without Repeating Characters" is a common problem in string manipulation and is often encountered in coding interviews. The challenge is to find the maximum length of a substring without any repeating characters within a given string. This problem tests the ability to track character occurrences and efficiently update the length of a substring.

Problem

Given a string s, the task is to find the length of the longest substring without repeating characters.

2. Solution Steps

1. Initialize a hash table (dictionary in Python) to store the last index of each character encountered.

2. Initialize variables to keep track of the starting point of the current substring and the maximum length found.

3. Iterate through the string, updating the hash table with each character's latest index.

4. If a repeating character is found, update the starting point of the current substring to the next position after the last occurrence of the repeating character.

5. Calculate and update the maximum length of the substring found so far.

6. Continue until the end of the string is reached.

7. Return the maximum length.

3. Code Program

def lengthOfLongestSubstring(s):
    char_index_map = {}
    max_length = start = 0

    for i, char in enumerate(s):
        if char in char_index_map and char_index_map[char] >= start:
            start = char_index_map[char] + 1
        char_index_map[char] = i
        max_length = max(max_length, i - start + 1)

    return max_length

# Example Usage
print(lengthOfLongestSubstring("abcabcbb"))  # Output: 3
print(lengthOfLongestSubstring("bbbbb"))     # Output: 1
print(lengthOfLongestSubstring("pwwkew"))    # Output: 3

Output:

3
1
3

Explanation:

1. Hash Table Usage: A hash table is used to store the last index where each character was seen.

2. Substring Tracking: The starting point of the current substring is updated whenever a repeating character is found.

3. Maximum Length Calculation: The length of the current substring is calculated by subtracting the starting index from the current index.

4. Efficient Traversal: The string is traversed once, ensuring O(n) time complexity.

5. Edge Cases Handling: The starting point of the substring is updated correctly to handle repeating characters.

6. Result: The function returns the length of the longest substring without repeating characters.