Longest Substring Without Repeating Characters - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Longest Substring Without Repeating Characters" Problem in Go

Difficulty: Medium | Tags: Hash Table, String, Sliding Window

Introduction

The problem requires finding the length of the longest substring without repeating characters in a given string. This is a classic sliding window problem that tests your ability to efficiently track and update character positions.

Problem Analysis

Given a string, we need to identify the longest contiguous substring where all characters are unique. For example, in "abcabcbb", the longest substring is "abc" with length 3. The challenge is to solve this efficiently for large input sizes.

Solution Approach

We use a sliding window technique with a hash map to track the last seen index of each character. As we iterate through the string, we adjust the window's start position whenever we encounter a duplicate character. This ensures we always maintain a window of unique characters while tracking the maximum length found.

Go Implementation


func lengthOfLongestSubstring(s string) int {
    charIndexMap := make(map[byte]int)
    maxLength := 0
    start := 0
    for end := 0; end < len(s); end++ {
        currentChar := s[end]
        if lastIndex, exists := charIndexMap[currentChar]; exists && lastIndex >= start {
            start = lastIndex + 1
        }
        charIndexMap[currentChar] = end
        currentLength := end - start + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }
    return maxLength
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. We traverse the string once, and each character is processed in constant time.

Space Complexity: O(min(m, n)), where m is the size of the character set (ASCII has 128 characters). In the worst case, we store all unique characters in the hash map.

Testing and Examples

Test cases:

  • "abcabcbb" → 3
  • "bbbbb" → 1
  • "pwwkew" → 3
  • "" → 0
  • " " → 1

Best Practices and Tips

1. Use a sliding window to efficiently track the current substring.
2. Leverage a hash map for O(1) lookups of character indices.
3. Always update the start position when a duplicate is found.
4. Consider edge cases like empty strings or strings with spaces.

Read more