Length of Longest Substring Without Repeating Characters

Given a string s, your task is to find the length of the longest substring that contains no repeating characters.

If the string is empty, return 0.

For example:

Input: s = "abcabcbb" → Output: 3 (The answer is "abc")

Understanding the Problem

We are given a string s, and our goal is to find the length of the longest substring that contains no repeating characters. A substring is a contiguous block of characters from the string, and "no repeating characters" means each character must appear only once in that block.

For example, in the string "abcabcbb", the longest such substring is "abc", which has a length of 3.

This is a common sliding window problem — a technique that lets us move through the string efficiently while maintaining a valid "window" of non-repeating characters.

Step-by-Step Solution with Example

Step 1: Initialize variables

We use two pointers: start to indicate the start of the current window and i to iterate through the string.

We also use a map called charIndexMap to store the most recent index of each character we've seen.

We initialize maxLen = 0 to store the length of the longest substring found.

Step 2: Traverse the string

Start with the example: s = "abcabcbb"

• Start with start = 0, maxLen = 0
• At i = 0: character is 'a' → not seen before → update map: {a: 0}, window is "a" → maxLen = 1
• At i = 1: character is 'b' → not seen before → map: {a: 0, b: 1}, window: "ab" → maxLen = 2
• At i = 2: character is 'c' → not seen → map: {a: 0, b: 1, c: 2}, window: "abc" → maxLen = 3
• At i = 3: character is 'a' → seen at index 0, which is ≥ start (0) → update start = 1 → map: {a: 3, b: 1, c: 2}, window: "bca"
• At i = 4: character is 'b' → seen at index 1, which is ≥ start (1) → update start = 2 → map: {a: 3, b: 4, c: 2}, window: "cab"
• At i = 5: character is 'c' → seen at index 2 → update start = 3 → map: {a: 3, b: 4, c: 5}, window: "abc"
• At i = 6: character is 'b' → seen at index 4 → update start = 5 → map: {a: 3, b: 6, c: 5}, window: "cb"
• At i = 7: character is 'b' → seen at index 6 → update start = 7 → map: {a: 3, b: 7, c: 5}, window: "b"

Throughout this process, the maximum length of a window with all unique characters we saw was 3.

Step 3: Return the result

After processing all characters, return maxLen which holds the length of the longest valid substring.

Edge Cases

• Empty string: If s = "", there are no characters, so return 0.
• All same characters: If s = "aaaa", the longest substring without repeating characters is "a", so return 1.
• All unique characters: If s = "abcdef", no character repeats, so return the length of the whole string → 6.
• String with spaces or symbols: Spaces and symbols are also treated as characters, so "a b c a b" would be processed similarly.

Final Thoughts

This problem is efficiently solved using the sliding window technique. It avoids nested loops by adjusting the window dynamically as we encounter repeating characters, resulting in a time complexity of O(n).

By using a map to store the last seen index of each character, we ensure we always know where to move the window's start. This approach is beginner-friendly once you understand the idea of a window sliding over the string and adjusting as needed to maintain uniqueness.

1. Initialize a hash set or map charIndexMap to track characters and their most recent indices.
2. Use two pointers: start for the beginning of the current window, and i for the current character index.
3. Initialize maxLen = 0 to store the length of the longest valid substring.
4. Traverse the string using index i from 0 to end of string:
5. → If s[i] is already in charIndexMap and its last index is ≥ start, update start = charIndexMap[s[i]] + 1.
6. → Update or insert s[i] in charIndexMap with the current index i.
7. → Update maxLen = max(maxLen, i - start + 1).
8. After the loop ends, return maxLen as the final answer.

#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(char* s) {
    int lastIndex[256];
    for (int i = 0; i < 256; i++) lastIndex[i] = -1;

    int maxLen = 0, start = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        unsigned char ch = s[i];
        if (lastIndex[ch] >= start) {
            start = lastIndex[ch] + 1;
        }
        lastIndex[ch] = i;
        int windowLen = i - start + 1;
        if (windowLen > maxLen) maxLen = windowLen;
    }
    return maxLen;
}

int main() {
    char s[] = "abcabcbb";
    int result = lengthOfLongestSubstring(s);
    printf("Length of longest substring without repeating characters: %d\n", result);
    return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(const string& s) {
    unordered_map<char, int> charIndexMap;
    int maxLen = 0, start = 0;
    for (int i = 0; i < s.length(); i++) {
        if (charIndexMap.find(s[i]) != charIndexMap.end() && charIndexMap[s[i]] >= start) {
            start = charIndexMap[s[i]] + 1;
        }
        charIndexMap[s[i]] = i;
        maxLen = max(maxLen, i - start + 1);
    }
    return maxLen;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of longest substring without repeating characters: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

def length_of_longest_substring(s: str) -> int:
    char_index_map = {}
    max_len = 0
    start = 0
    for i, ch in enumerate(s):
        if ch in char_index_map and char_index_map[ch] >= start:
            start = char_index_map[ch] + 1
        char_index_map[ch] = i
        max_len = max(max_len, i - start + 1)
    return max_len

# Example usage
s = "abcabcbb"
print("Length of longest substring without repeating characters:", length_of_longest_substring(s))

import java.util.HashMap;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int maxLen = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (charIndexMap.containsKey(ch) && charIndexMap.get(ch) >= start) {
                start = charIndexMap.get(ch) + 1;
            }
            charIndexMap.put(ch, i);
            maxLen = Math.max(maxLen, i - start + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Length of longest substring without repeating characters: " + lengthOfLongestSubstring(s));
    }
}

function lengthOfLongestSubstring(s) {
  const charIndexMap = new Map();
  let maxLen = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (charIndexMap.has(ch) && charIndexMap.get(ch) >= start) {
      start = charIndexMap.get(ch) + 1;
    }
    charIndexMap.set(ch, i);
    maxLen = Math.max(maxLen, i - start + 1);
  }

  return maxLen;
}

// Example usage
const s = "abcabcbb";
console.log("Length of longest substring without repeating characters:", lengthOfLongestSubstring(s));

package main

import "fmt"

func lengthOfLongestSubstring(s string) int {
    lastIndex := make(map[rune]int)
    maxLen, start := 0, 0

    for i, ch := range s {
        if idx, found := lastIndex[ch]; found && idx >= start {
            start = idx + 1
        }
        lastIndex[ch] = i
        windowLen := i - start + 1
        if windowLen > maxLen {
            maxLen = windowLen
        }
    }
    return maxLen
}

func main() {
    s := "abcabcbb"
    fmt.Printf("Length of longest substring without repeating characters: %d\n", lengthOfLongestSubstring(s))
}

use std::collections::HashMap;

fn length_of_longest_substring(s: &str) -> usize {
    let mut char_index_map = HashMap::new();
    let mut max_len = 0;
    let mut start = 0;

    for (i, ch) in s.chars().enumerate() {
        if let Some(&prev_index) = char_index_map.get(&ch) {
            if prev_index >= start {
                start = prev_index + 1;
            }
        }
        char_index_map.insert(ch, i);
        max_len = max_len.max(i - start + 1);
    }

    max_len
}

fn main() {
    let s = "abcabcbb";
    println!("Length of longest substring without repeating characters: {}", length_of_longest_substring(s));
}

fun lengthOfLongestSubstring(s: String): Int {
    val charIndexMap = mutableMapOf<Char, Int>()
    var maxLen = 0
    var start = 0

    for (i in s.indices) {
        val ch = s[i]
        if (charIndexMap.containsKey(ch) && charIndexMap[ch]!! >= start) {
            start = charIndexMap[ch]!! + 1
        }
        charIndexMap[ch] = i
        maxLen = maxOf(maxLen, i - start + 1)
    }

    return maxLen
}

fun main() {
    val s = "abcabcbb"
    println("Length of longest substring without repeating characters: ${lengthOfLongestSubstring(s)}")
}

func lengthOfLongestSubstring(_ s: String) -> Int {
    var charIndexMap = [Character: String.Index]()
    var maxLen = 0
    var start = s.startIndex

    for current in s.indices {
        let ch = s[current]
        if let prevIndex = charIndexMap[ch], prevIndex >= start {
            start = s.index(after: prevIndex)
        }
        charIndexMap[ch] = current
        maxLen = max(maxLen, s.distance(from: start, to: s.index(after: current)))
    }
    return maxLen
}

let s = "abcabcbb"
print("Length of longest substring without repeating characters: \(lengthOfLongestSubstring(s))")

function lengthOfLongestSubstring(s: string): number {
  const charIndexMap: Map<string, number> = new Map();
  let maxLen = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (charIndexMap.has(ch) && charIndexMap.get(ch)! >= start) {
      start = charIndexMap.get(ch)! + 1;
    }
    charIndexMap.set(ch, i);
    maxLen = Math.max(maxLen, i - start + 1);
  }

  return maxLen;
}

// Example usage
const s = "abcabcbb";
console.log("Length of longest substring without repeating characters:", lengthOfLongestSubstring(s));

Time complexity

Space complexity

O(min(n, m))

The hash map stores at most 'm' unique characters, where 'm' is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII). In the worst case, it stores all 'n' characters of the string if they are all unique. Hence, the space complexity is O(min(n, m)).