DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 44: Python Longest Substring Finder, Sliding Window Technique for Non-Repeating Characters Length

#challenge #python #intermediate #programming

Welcome to Day 44 of the #80DaysOfChallenges journey! This intermediate challenge introduces the sliding window technique to find the length of the longest substring without repeating characters, using a set to track unique chars in the current window and adjusting pointers for efficiency in O(n) time. It's a cornerstone algorithm for string problems, teaching dynamic window management, set operations for uniqueness, and max tracking, common in interviews and optimization tasks. If you're transitioning from basic strings to algorithmic patterns or tackling LeetCode-style questions, this "Python longest substring" script showcases a function that's optimal, concise, and adaptable for variants like k-unique chars or min window.

💡 Key Takeaways from Day 44: Longest Substring Function

This task centers on a function that scans the string with two pointers, expanding the right while shrinking the left on duplicates, using a set for O(1) checks. It's a classic sliding window: maintain invariant (no repeats), update max. We'll detail: function with set and pointers, loop for window adjustment, and main with input and result.

1. Function Design: Set for Unique Tracking

The length_of_longest_substring function takes a string and returns the max length:

def length_of_longest_substring(s: str) -> int:
    """
    Return the length of the longest substring without duplicates.
    Sliding window approach using a set for current window characters.
    """
    char_set = set()  # Set for current window characters
    left = 0
    max_length = 0
Enter fullscreen mode Exit fullscreen mode

Set holds chars in window for fast add/remove/check. Left pointer starts at 0, max tracks longest.

2. Loop Processing: Expand and Shrink Window

Core loop scans with right pointer:

for right in range(len(s)):
    while s[right] in char_set:  # If duplicate, shrink window from left
        char_set.remove(s[left])
        left += 1
    char_set.add(s[right])
    max_length = max(max_length, right - left + 1)

return max_length
Enter fullscreen mode Exit fullscreen mode

For each right, while duplicate, remove from left and increment left. Add right, update max with window size (right - left + 1). For "abcabcbb": max=3 ("abc"). O(n) as each char visited at most twice.

3. Main Interactive: Input and Output

Script prompts and calls:

input_str = input("Enter a string: ").strip()
result = length_of_longest_substring(input_str)
print(f"Result: {result}")
Enter fullscreen mode Exit fullscreen mode

Strip cleans, calls function, prints length. Simple, could add substring finding.

🎯 Summary and Reflections

This longest substring finder exemplifies sliding window power for optimization. It reinforced:

  • Set utility: O(1) for uniqueness in window.
  • Pointer dynamics: Left/right for adjustable range.
  • Efficiency focus: O(n) over brute O(n^2).

Reflections: Core to many string algos. For fun, find actual substring.

Advanced Alternatives: Dict for last index, jump left: left = max(left, last[char]+1). Or deque for order. Your window trick? Share!

🚀 Next Steps and Resources

Day 44 boosted algo skills, prepping for patterns. In #80DaysOfChallenges? Variants? Post!

Top comments (0)