Longest Substring Without Repeating Characters - Python Solution

1. Introduction

The "Longest Substring Without Repeating Characters" problem is a common challenge in string processing and algorithmic interviews. It tests the ability to understand and manipulate substrings and requires the use of data structures to track characters efficiently. This problem is key in applications that involve text analysis or pattern recognition.

Problem

Given a string s, the task is to find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within a string, differing from a subsequence.

2. Solution Steps

1. Use a sliding window approach to maintain a range of characters without duplicates.

2. Create a hash map (or set) to keep track of the characters in the current window and their indices.

3. Initialize two pointers, start and end, representing the start and end of the current window, respectively.

4. Iterate through the string using the end pointer.

5. If a character is repeated, move the start pointer to the right of the first occurrence of this character.

6. Update the maximum length at each step.

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

3. Code Program

def lengthOfLongestSubstring(s):
    charMap = {}
    start = maxLength = 0

    for end, char in enumerate(s):
        if char in charMap and charMap[char] >= start:
            start = charMap[char] + 1
        charMap[char] = end
        maxLength = max(maxLength, end - start + 1)

    return maxLength

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

Output:

3
1
3

Explanation:

1. Sliding Window Technique: Dynamically adjusts the window to exclude repeating characters.

2. Hash Map for Tracking: Maintains characters' indices to identify repeats quickly.

3. Window Adjustment: Moves the start pointer to exclude previous occurrences of a character.

4. Maximum Length Calculation: Continuously updates the maximum substring length.

5. Efficient Solution: The approach has O(n) time complexity, where n is the length of the string.

6. Applicability: Demonstrates a pattern useful in various string processing scenarios, such as parsing and text analysis.