NUHMAN.com

Introduction

The "Longest Substring Without Repeating Characters" is a popular problem to test your understanding of string manipulation and sliding window technique. It’s often asked in coding interviews due to its mix of logic and optimization. In this article, we'll solve LeetCode 3 in Go (Golang) using an efficient method and explain each step clearly.

Problem Statement

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

Example

go

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Understanding the Problem

You are to return the length of the longest substring that contains no duplicate characters.

This doesn’t mean the longest unique set of characters in the string, but the longest continuous substring without repeating characters.

Brute Force Approach (Inefficient)

You could generate all substrings and check each for uniqueness, but that leads to O(n²) time and space — too slow for large strings.

Optimized Approach: Sliding Window

The sliding window technique lets you move through the string while tracking the current window of unique characters.

Algorithm Steps:

1. Use a map charIndex to store the last seen index of each character.
2. Maintain a window with two pointers:

• start: beginning index of the current substring.
• i: current character index.

1. When you see a duplicate character:

• Move the start pointer to charIndex[s[i]] + 1 only if it's ahead of current start.

1. Update the maxLength as you move.
2. Return maxLength.

Go Implementation

go

package main

import (
    "fmt"
)

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[rune]int)
    maxLength := 0
    start := 0

    for i, char := range s {
        if lastIndex, found := charIndex[char]; found && lastIndex >= start {
            start = lastIndex + 1
        }
        charIndex[char] = i
        if i-start+1 > maxLength {
            maxLength = i - start + 1
        }
    }

    return maxLength
}

func main() {
    input := "abcabcbb"
    result := lengthOfLongestSubstring(input)
    fmt.Printf("Longest substring without repeating characters: %d\n", result)
}

Example Walkthrough

Input: "abcabcbb"

1. a → unique → window = "a", length = 1
2. b → unique → window = "ab", length = 2
3. c → unique → window = "abc", length = 3
4. a again → duplicate → move start to 1
5. → window = "bca", still length = 3
6. And so on...

Final result: 3

Time and Space Complexity

• Time Complexity: O(n) — each character is processed at most twice (once added, once skipped).
• Space Complexity: O(k) — where k is the number of unique characters (max 26–128 depending on charset).

Key Takeaways

• Sliding window + hash map is the go-to strategy for substring uniqueness problems.
• Be careful with pointer movements to avoid infinite loops or skipped characters.
• Works efficiently for large input strings (up to 10⁵ characters).