Longest Substring Without Repeating Characters

Hash Table Medium 19 views

Like0

Longest Substring Without Repeating Characters asks for the maximum length of a contiguous substring containing unique characters only. As you scan the string, duplicates force the valid window to shift forward. The task is to track the longest unique window length, not the substring content itself.

The standard linear solution uses a sliding window with a map of last seen indices. Move the right pointer through the string; when the current character was seen inside the active window, move left boundary to one position after that previous index. Update the last-seen index and record the best window size after each step.

Judge includes repeated-character runs, alternating repeat patterns, empty strings, and mixed cases where the best window appears in the middle. Return one integer length. Correctness depends on never moving the left boundary backward and handling duplicate hits relative to current window start. With those rules, the algorithm runs in O(n) time and remains stable for long strings with heavy repetition.

When duplicates appear, only move the left boundary if the previous occurrence is inside the current window; older occurrences outside the window should be ignored. This condition prevents accidental over-shrinking and is the difference between correct O(n) behavior and subtle length underestimation.

Examples

Example 1

Input

s = "abcabcbb"

Output

Explanation

Longest unique substring is "abc".

Example 2

Input

s = "bbbbb"

Output

Explanation

Longest unique substring is "b".

Example 3

Input

s = "pwwkew"

Output

Explanation

Longest unique substring is "wke".

Algorithm Flow

Recommendation Algorithm Flow for Longest Substring Without Repeating Characters - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int longest_substring_without_repeating_characters(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (last.containsKey(ch) && last.get(ch) >= left) {
                left = last.get(ch) + 1;
            }
            last.put(ch, right);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

javascript

function longest_substring_without_repeating_characters(s) {
    const last = {};
    let left = 0, ans = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        if (last[ch] !== undefined && last[ch] >= left) {
            left = last[ch] + 1;
        }
        last[ch] = right;
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

php

<?php
function longest_substring_without_repeating_characters($s) {
    $last = [];
    $left = 0;
    $ans = 0;
    $n = strlen($s);
    for ($right = 0; $right < $n; $right++) {
        $ch = $s[$right];
        if (isset($last[$ch]) && $last[$ch] >= $left) {
            $left = $last[$ch] + 1;
        }
        $last[$ch] = $right;
        $cur = $right - $left + 1;
        if ($cur > $ans) $ans = $cur;
    }
    return $ans;
}
?>

python

def longest_substring_without_repeating_characters(s: str) -> int:
    last = {}
    left = 0
    ans = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        ans = max(ans, right - left + 1)
    return ans

rust

use std::collections::HashMap;
fn longest_substring_without_repeating_characters(s: String) -> i32 {
    let mut last: HashMap<char, i32> = HashMap::new();
    let mut left: i32 = 0;
    let mut ans: i32 = 0;
    let chars: Vec<char> = s.chars().collect();
    for right in 0..chars.len() {
        let ch = chars[right];
        if let Some(pos) = last.get(&ch) {
            if *pos >= left {
                left = *pos + 1;
            }
        }
        last.insert(ch, right as i32);
        let cur = right as i32 - left + 1;
        if cur > ans { ans = cur; }
    }
    ans
}

typescript

function longest_substring_without_repeating_characters(s: string): number {
    var last: { [key: string]: number } = {};
    var left = 0, ans = 0;
    for (var right = 0; right < s.length; right++) {
        var ch = s.charAt(right);
        if (last[ch] !== undefined && last[ch] >= left) {
            left = last[ch] + 1;
        }
        last[ch] = right;
        var cur = right - left + 1;
        if (cur > ans) ans = cur;
    }
    return ans;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Longest Substring Without Repeating Characters

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion