← Back to DevBytes
Go August 06, 2026 9 min read

Solving Longest Substring Without Repeating in Go: Step-by-Step Guide

Introduction to the Longest Substring Without Repeating Characters Problem

The "Longest Substring Without Repeating Characters" is one of the most classic algorithmic problems you will encounter in coding interviews and competitive programming. Given a string, the goal is to find the length of the longest contiguous substring that contains no duplicate characters. For example, in the string "abcabcbb", the answer is 3, because the longest substring without repeating characters is "abc".

This problem tests your understanding of string manipulation, hash maps, and the sliding window technique. In this tutorial, we will explore how to solve it efficiently in Go, walking through the naive approach first and then optimizing it to an O(n) solution.

Why This Problem Matters

Beyond being a common interview question at companies like Google, Amazon, and Microsoft, this problem has real-world applications. It is relevant in scenarios such as:

Mastering this problem also builds a strong foundation for the sliding window pattern, which is applicable to dozens of other problems involving arrays and strings.

Understanding the Problem Statement

Given an input string s, return the length of the longest substring that contains no repeating characters. A substring is a contiguous sequence of characters within the string. Note that the answer is the length, not the substring itself.

Here are a few examples to clarify:

The Brute Force Approach

The most intuitive solution is to generate every possible substring and check each one for duplicate characters. While this works, it is inefficient. The time complexity is O(nΒ³) in the worst case because there are O(nΒ²) substrings and checking each for duplicates takes O(n) time.

Here is a basic brute force implementation in Go:

package main

import "fmt"

func hasUniqueChars(s string, start, end int) bool {
    seen := make(map[byte]bool)
    for i := start; i <= end; i++ {
        if seen[s[i]] {
            return false
        }
        seen[s[i]] = true
    }
    return true
}

func lengthOfLongestSubstringBrute(s string) int {
    maxLen := 0
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            if hasUniqueChars(s, i, j) {
                if j-i+1 > maxLen {
                    maxLen = j - i + 1
                }
            } else {
                break
            }
        }
    }
    return maxLen
}

func main() {
    fmt.Println(lengthOfLongestSubstringBrute("abcabcbb")) // Output: 3
}

This approach is acceptable for very short strings but will time out on longer inputs. We need a more efficient strategy.

The Sliding Window Technique

The sliding window technique is the key to solving this problem optimally. The idea is to maintain a window (defined by two pointers, left and right) that always contains a substring without repeating characters. As we expand the window by moving right, if we encounter a duplicate, we shrink the window from the left until the duplicate is removed.

We use a hash map to store the last seen index of each character. This allows us to instantly know where a duplicate was last found and jump the left pointer past it, avoiding unnecessary iterations.

How the Sliding Window Works

Imagine the string "abcabcbb":

Optimal Solution in Go

Here is the complete, optimized solution using the sliding window technique with a hash map:

package main

import "fmt"

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[byte]int)
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        char := s[right]
        // If the character was seen and is within the current window
        if idx, found := charIndex[char]; found && idx >= left {
            left = idx + 1
        }
        charIndex[char] = right
        currentLen := right - left + 1
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

func main() {
    testCases := []string{
        "abcabcbb",
        "bbbbb",
        "pwwkew",
        "",
        " ",
        "dvdf",
    }

    for _, tc := range testCases {
        fmt.Printf("Input: %q -> Output: %d\n", tc, lengthOfLongestSubstring(tc))
    }
}

When you run this program, the output will be:

Input: "abcabcbb" -> Output: 3
Input: "bbbbb" -> Output: 1
Input: "pwwkew" -> Output: 3
Input: "" -> Output: 0
Input: " " -> Output: 1
Input: "dvdf" -> Output: 3

Breaking Down the Code

Let us examine each part of the solution:

Complexity Analysis

Understanding the time and space complexity of your solution is essential, especially in interviews:

Compare this to the brute force approach, which was O(nΒ³) in time. The sliding window reduces this dramatically while keeping space usage minimal.

Handling Unicode Characters

The solution above uses byte, which works for ASCII strings. However, Go strings are UTF-8 encoded, and a single Unicode character (rune) can occupy multiple bytes. If your input contains characters like emojis or non-Latin scripts, you should use rune instead of byte.

Here is the Unicode-safe version:

package main

import "fmt"

func lengthOfLongestSubstringUnicode(s string) int {
    charIndex := make(map[rune]int)
    maxLen := 0
    left := 0

    for right, char := range s {
        if idx, found := charIndex[char]; found && idx >= left {
            left = idx + 1
        }
        charIndex[char] = right
        currentLen := right - left + 1
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

func main() {
    fmt.Println(lengthOfLongestSubstringUnicode("abcabcbb"))  // Output: 3
    fmt.Println(lengthOfLongestSubstringUnicode("δ½ ε₯½δΈ–η•Œδ½ ε₯½"))  // Output: 4
    fmt.Println(lengthOfLongestSubstringUnicode("πŸ˜€πŸ˜πŸ˜‚πŸ˜ƒπŸ˜€"))  // Output: 4
}

Using range over a string in Go automatically iterates over runes, decoding UTF-8 properly. This makes the solution robust for international text.

Alternative Approach: Using a Fixed-Size Array

If you know the input only contains ASCII characters, you can replace the hash map with a fixed-size array of 128 integers. This avoids hash map overhead and can be slightly faster in practice.

package main

import "fmt"

func lengthOfLongestSubstringASCII(s string) int {
    // -1 means the character has not been seen
    charIndex := [128]int{}
    for i := range charIndex {
        charIndex[i] = -1
    }

    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        char := s[right]
        if charIndex[char] >= left {
            left = charIndex[char] + 1
        }
        charIndex[char] = right
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

func main() {
    fmt.Println(lengthOfLongestSubstringASCII("abcabcbb")) // Output: 3
}

This version has the same time complexity but uses a predictable, stack-allocated array instead of a heap-allocated map. For performance-critical applications processing large volumes of ASCII text, this can be a meaningful optimization.

Best Practices

When implementing this solution, keep the following best practices in mind:

Writing Tests for the Solution

A robust solution deserves robust tests. Here is an example of a table-driven test using Go's standard testing package:

package main

import "testing"

func TestLengthOfLongestSubstring(t *testing.T) {
    tests := []struct {
        name     string
        input    string
        expected int
    }{
        {"standard case", "abcabcbb", 3},
        {"all same chars", "bbbbb", 1},
        {"mixed case", "pwwkew", 3},
        {"empty string", "", 0},
        {"single char", "a", 1},
        {"single space", " ", 1},
        {"no repeats", "abcdef", 6},
        {"repeat at end", "dvdf", 3},
        {"unicode", "δ½ ε₯½δΈ–η•Œδ½ ε₯½", 4},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := lengthOfLongestSubstringUnicode(tt.input)
            if result != tt.expected {
                t.Errorf("got %d, want %d for input %q", result, tt.expected, tt.input)
            }
        })
    }
}

Run the tests with go test -v to see detailed output for each case. Table-driven tests make it trivial to add new cases as you discover edge cases in production.

Common Mistakes to Avoid

When solving this problem, developers often make a few recurring mistakes:

Conclusion

The Longest Substring Without Repeating Characters problem is an excellent exercise in mastering the sliding window pattern, a technique that appears in countless string and array problems. By using a hash map to track character positions and two pointers to define the window, we achieve an elegant O(n) solution in Go. Whether you choose the map-based approach for its clarity or the array-based approach for its performance, the key insight remains the same: maintain a valid window and adjust it efficiently when duplicates are found. Practice this pattern, write thorough tests, and you will be well-prepared to tackle similar challenges in both interviews and real-world applications.

β€” Ad β€”

Google AdSense will appear here after approval

← Back to all articles