Problem: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example:

Input: "abcabcbb"

Output: 3

Explanation: The longest substring without repeating characters is "abc", which has a length of 3.

Solution:

One approach to solve this problem is by using the sliding window technique. We can maintain a sliding window that contains all unique characters and dynamically update the window as we iterate through the string.

Here are the step-by-step explanations for the solution:

1. Initialize two pointers, start and end, both pointing to the start of the string.
2. Initialize a variable maxLength to keep track of the maximum length of the substring without repeating characters.
3. Initialize an empty set uniqueChars to store unique characters in the current window.
4. Iterate through the string using the end pointer until it reaches the end of the string.
5. Check if the character at the end pointer is already present in the uniqueChars set.
   • If yes, it means we have found a repeating character. We need to move the start pointer forward and remove the characters from the uniqueChars set until the repeating character is no longer present in the current window. Move the start pointer one step forward.
   • If no, it means the current character is unique. Add it to the uniqueChars set and calculate the length of the current window by subtracting the start pointer from the end pointer. Update maxLength if the current window length is greater than maxLength.
6. Repeat steps 4-5 until the end pointer reaches the end of the string.
7. Return the value of maxLength as the length of the longest substring without repeating characters.

Here is the implementation of the solution in Python:

def lengthOfLongestSubstring(s: str) -> int:
    start = 0
    end = 0
    maxLength = 0
    uniqueChars = set()

    while end < len(s):
        if s[end] in uniqueChars:
            uniqueChars.remove(s[start])
            start += 1
        else:
            uniqueChars.add(s[end])
            maxLength = max(maxLength, end - start + 1)
            end += 1
    
    return maxLength

The time complexity of this solution is O(n), where n is the length of the input string. We only iterate through the string once and perform constant-time operations.

The space complexity of this solution is O(min(n, m)), where n is the length of the input string and m is the size of the character set. In the worst case, when all characters are unique, the space required would be O(n).