3. Longest Substring Without Repeating Characters

Intuition

To find the length of the longest substring without repeating characters, we can use a sliding window approach. This allows us to efficiently manage the window of characters currently being considered and quickly adjust when we encounter a repeating character.

Approach

1. Initialize Variables: - char_map: A dictionary to store the latest index of each character. - max_length: An integer to keep track of the maximum length of substrings found. - start: An integer to mark the starting index of the current window of characters.
2. Sliding Window Technique: - Iterate through the string using a variable end as the end index of the current window. - For each character at index end: - If the character is already in char_map, update start to the maximum of start and the index after the last occurrence of the character. This effectively shrinks the window from the left to remove the repeating character. - Update char_map with the current index end for the character. - Update max_length to the maximum of max_length and the length of the current window (end - start + 1).
3. Return Result: - After iterating through the string, return max_length, which contains the length of the longest substring without repeating characters.

Complexity

Time Complexity:

O(n), where n is the length of the string. Each character is processed at most twice (once by the end pointer and once by the start pointer).

Space Complexity:

O(min(m, n)), where m is the size of the character set and n is the length of the string. This is because the dictionary will store at most min(m, n) characters.

Code

C++

#include 
#include 
#include 
using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        if (n == 0) return 0;
        unordered_map map;
        int maxLength = 0;
        int start = 0;
        for (int end = 0; end < n; end++) {
            char c = s[end];
            if (map.find(c) != map.end()) {
                start = max(start, map[c] + 1);
            }
            map[c] = end;
            maxLength = max(maxLength, end - start + 1);
        }
        return maxLength;
    }
};

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        char_map = {}
        max_length = 0
        start = 0
        for end in range(n):
            if s[end] in char_map:
                start = max(start, char_map[s[end]] + 1)
            char_map[s[end]] = end
            max_length = max(max_length, end - start + 1)
        return max_length

Java

import java.util.HashMap;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        HashMap map = new HashMap<>();
        int maxLength = 0;
        int start = 0;
        for (int end = 0; end < n; end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c) + 1);
            }
            map.put(c, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

JavaScript

var lengthOfLongestSubstring = function(s) {
    const n = s.length;
    if (n === 0) return 0;
    
    const charMap = new Map();
    let maxLength = 0;
    let start = 0;
    
    for (let end = 0; end < n; end++) {
        if (charMap.has(s[end])) {
            start = Math.max(start, charMap.get(s[end]) + 1);
        }
        charMap.set(s[end], end);
        maxLength = Math.max(maxLength, end - start + 1);
    }
    
    return maxLength;
};