LeetCode #3 Solution: Longest Substring

LeetCode #3 Solution – Longest Substring Without Repeating Characters: The challenge is to find the length of the longest substring in a given string s that contains no repeating characters. A substring is a contiguous sequence of characters within a string.

Examples:

Input: s = “abcabcbb”
Output: 3
Explanation: The longest substring without repeating characters is “abc”, which has a length of 3.

Input: s = “bbbbb”
Output: 1
Explanation: The longest substring without repeating characters is “b”, with a length of 1.

Input: s = “pwwkew”
Output: 3
Explanation: The longest substring without repeating characters is “wke”, length 3.

Note: The answer must be a substring, not a subsequence.

Approach Discussion

To solve this problem, we need to consider all possible substrings and find the one with the maximum length that doesn’t have any repeating characters.

Brute Force Approach

Idea: Generate all possible substrings and check each one for duplicate characters. This approach is too slow for large input strings due to its cubic time complexity. It would fail on LeetCode:

def lengthOfLongestSubstring(s):
    n = len(s)
    max_length = 0
    for i in range(n):
        for j in range(i+1, n+1):
            substring = s[i:j]
            if len(set(substring)) == len(substring):
                max_length = max(max_length, j - i)
    return max_length

Optimized Approach: Sliding Window

To improve efficiency, we can use the sliding window technique with a hash map. Use two pointers (left and right) to create a window that represents the current substring without duplicates.

def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_length = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    return max_length

Ideal Data Structure and Algorithm

Data Structure: Hash Map (Dictionary). It allows O(1) access and updates, essential for keeping track of characters and their indices efficiently.

Algorithm: Sliding Window with Hash Map. This method efficiently handles large strings by ensuring each character is visited at most twice, resulting in linear time complexity.

Introduction to the Sliding Window Algorithm

The sliding window is a technique that involves moving a window over data to solve problems involving contiguous sequences, like substrings or subarrays.

How It Works:

1. Initialize: Set two pointers (left and right) at the start of the string.
2. Expand Window: Move right to include new characters.
3. Shrink Window: If a duplicate is found, move left to exclude the previous occurrence.
4. Update Records: Keep track of the maximum length found.

This method ensures we only traverse the string once, achieving O(n) time complexity.

Step-by-Step Solution for LeetCode #3 Problem

Let’s dive into the implementation with detailed explanations.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Dictionary to store the last positions of occurrence
        char_index_map = {}
        max_length = 0
        # The starting point of the current substring
        left = 0

        # Loop over the string
        for right, char in enumerate(s):
            # If the character is found in the map and is within the current window
            if char in char_index_map and char_index_map[char] >= left:
                # Move the left pointer to the right of the previous occurrence
                left = char_index_map[char] + 1
            # Update or add the character's index
            char_index_map[char] = right
            # Update the maximum length
            max_length = max(max_length, right - left + 1)

        return max_length

Explanation:

• Variables:
  • char_index_map: Stores the latest index of each character.
  • max_length: Keeps track of the maximum length found.
  • left: Marks the start of the current window.
• Process:
  1. Iterate over each character in the string with its index.
  2. Check if the character is in char_index_map and its last occurrence index is greater than or equal to left.
     • Yes: There’s a duplicate in the current window.
       • Action: Move left to char_index_map[char] + 1 to start a new window after the previous occurrence.
     • No: No duplicate in the current window.
  3. Update char_index_map[char] with the current index right.
  4. Calculate the length of the current window (right - left + 1) and update max_length if it’s larger.

Example Walkthrough:

Let’s apply the algorithm to s = "abcabcbb".

1. Initialize:
   • char_index_map = {}
   • left = 0
   • max_length = 0
2. First Iteration (right = 0, char = 'a'):
   • 'a' not in char_index_map.
   • Update char_index_map = {'a': 0}.
   • Update max_length = max(0, 0 - 0 + 1) = 1.
3. Second Iteration (right = 1, char = 'b'):
   • 'b' not in char_index_map.
   • Update char_index_map = {'a': 0, 'b': 1}.
   • Update max_length = max(1, 1 - 0 + 1) = 2.
4. Third Iteration (right = 2, char = 'c'):
   • 'c' not in char_index_map.
   • Update char_index_map = {'a': 0, 'b': 1, 'c': 2}.
   • Update max_length = max(2, 2 - 0 + 1) = 3.
5. Fourth Iteration (right = 3, char = 'a'):
   • 'a' in char_index_map and char_index_map['a'] = 0 >= left.
   • Update left = char_index_map['a'] + 1 = 1.
   • Update char_index_map = {'a': 3, 'b': 1, 'c': 2}.
   • max_length remains 3.

Continue this process for the rest of the characters.

Optimization Tips

• Efficient Data Structures: Use a dictionary for constant-time lookups and updates.
• Avoid Nested Loops: The single-pass approach ensures O(n) time complexity.
• Clean Code Practices:
  • Use meaningful variable names.
  • Add comments for clarity.
  • Utilize Python’s built-in functions like enumerate for cleaner loops.

Conclusion

By employing the sliding window technique with a hash map, we’ve optimized the solution to run in linear time. This approach efficiently handles large input strings and is accepted on LeetCode.

Try It Yourself:

Test the function with different input strings to solidify your understanding.

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

---

Happy Coding!

Understanding this algorithm not only solves this problem but also equips you with a valuable technique applicable to various other string and array challenges.

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.