Longest Distinct Character Substring — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(k)

Problem Description

Given a string s, determine the maximum length of any contiguous substring of s that contains no repeated characters. The substring must consist of consecutive positions in s, and each character may appear at most once within the chosen segment. If s is null or empty, the result is 0.

DSA Pattern Breakdown

"Longest Distinct Character Substring"

medium

WHY DOES IT MATTER?

The sliding‑window / two‑pointer pattern is essential because many real‑world constraints—such as rate limiting, cache eviction windows, or streaming analytics—require processing contiguous segments efficiently without revisiting elements.

OPTIMIZATION CHALLENGE

The key insight is to jump the left pointer directly to the index after the previous occurrence of a duplicate, rather than incrementally moving it one step at a time, which collapses the quadratic blow‑up to linear time.

REAL-WORLD CONNECTION

Think of a network packet inspector that monitors a continuous stream of bytes and must flag the longest sequence without duplicate identifiers; moving a fixed‑size inspection window forward without re‑scanning the entire buffer mirrors this algorithm.

During an interview, write the hash map update and left‑pointer adjustment in a single line: left = Math.max(left, lastSeen.get(ch) + 1); this demonstrates both correctness (handling overlapping duplicates) and conciseness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem of finding the longest substring without repeating characters is a classic sliding‑window challenge. A naive solution would examine every possible start index and expand until a duplicate appears, leading to O(n²) time on strings of length n, which quickly becomes infeasible for large inputs such as logs or user‑generated text streams. The optimal paradigm leverages a dynamic window that expands rightward while maintaining a data structure (typically a hash map or an integer array for ASCII/Unicode code points) that records the most recent index of each character. When a duplicate is encountered inside the current window, the left boundary jumps directly to one position after the previous occurrence, preserving the invariant that the window always contains distinct characters. This approach ensures each character is processed at most twice—once when the right pointer visits it and possibly once when the left pointer skips past it—yielding linear O(n) time.

The sliding‑window technique is a concrete instance of the two‑pointer method, a broader algorithmic pattern used for problems involving contiguous subarrays or substrings with a monotonic property. By converting the “no‑repeat” constraint into a mutable boundary condition, we avoid recomputation and achieve optimal performance. The space usage is proportional to the size of the character set (e.g., 128 for ASCII or 256 for extended ASCII), which is constant relative to input size, making the solution both time‑ and space‑efficient for real‑world applications.

Interview Questions on This Problem

Q1How would you modify the algorithm to return the actual longest substring instead of just its length?

Maintain two additional indices: one to record the start of the best window found so far and another for its length. Whenever the current window length exceeds the best length, update these indices. After the scan, return s.substring(bestStart, bestStart + bestLength).

Q2What changes are needed if the input string can contain Unicode characters beyond the basic ASCII set?

Replace the fixed‑size integer array with a HashMap<Character, Integer> (or int[] sized to the full Unicode range if memory permits). The rest of the sliding‑window logic stays the same, but you must handle surrogate pairs correctly if using Java's char type.

Q3Can you solve the problem in O(n) time using only O(1) extra space, assuming the input consists solely of lowercase English letters?

Yes. Use an int[26] array to store last indices, which is constant space. The sliding‑window logic remains unchanged, giving O(n) time and O(1) auxiliary space.

Examples

Example 1

Input

abdefgabc

Output

Explanation: Scanning from the start, the characters 'a','b','d','e','f','g' are all distinct, giving a substring length of 6. The next character 'a' repeats a previous character, so the window must shrink; no longer distinct segment appears later. Hence the longest distinct substring length is 6.

Example 2

Input

aaaaa

Output

Explanation: Every character is 'a'. The longest substring without repetition can contain only a single 'a', so the answer is 1.

Example 3

Input

xyzabcz

Output

Explanation: Starting at index 0, the characters 'x','y','z','a','b','c' are all unique, forming a substring of length 6. The following character 'z' repeats the earlier 'z', breaking uniqueness. No later window exceeds length 6, so the result is 6.

Constraints

1 <= s.length <= 200000
s consists of printable ASCII characters (code 32 to 126)
The algorithm should run in O(n) time and O(k) extra space, where k is the size of the character set.

Optimal Approach & Strategy

Use a sliding window with a hash map that records the most recent index of each character, moving the left boundary forward only when a duplicate is found. This yields O(n) time and O(1) (or O(k)) space, where k is the character set size.

Brute Force Approach

Check every possible start index, expand the substring until a repeated character appears, and track the maximum length; this requires nested loops and results in O(n²) time. It also needs a set to detect duplicates for each start position.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (!s) return 0;
    
    const lastSeen = new Map();
    let left = 0;
    let maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        if (lastSeen.has(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }
        lastSeen.set(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        
        unordered_map<char, int> lastSeen;
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.size(); ++right) {
            char c = s[right];
            if (lastSeen.count(c) && lastSeen[c] >= left) {
                left = lastSeen[c] + 1;
            }
            lastSeen[c] = right;
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                left = lastSeen.get(c) + 1;
            }
            lastSeen.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        
        last_seen = {}
        left = 0
        max_len = 0
        
        for right, c in enumerate(s):
            if c in last_seen and last_seen[c] >= left:
                left = last_seen[c] + 1
            last_seen[c] = right
            max_len = max(max_len, right - left + 1)
        
        return max_len

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (!s) return 0;
    
    const lastSeen = new Map();
    let left = 0;
    let maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        if (lastSeen.has(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }
        lastSeen.set(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Longest Distinct Character Substring Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Longest Distinct Character Substring — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor