Longest substring without repeating Medium ​

Question ​

Given a string s, find the length of the longest substring without repeating characters

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

def length_of_longest_substring(s):
    start = 0
    max_length = 0
    char_index_map = {}  # Dictionary to store the last index of each character in the string

    for i in range(len(s)):
        if s[i] in char_index_map and char_index_map[s[i]] >= start:
            start = char_index_map[s[i]] + 1
        char_index_map[s[i]] = i
        max_length = max(max_length, i - start + 1)

    return max_length

# Test the function
s = "abcabcbb"
print(length_of_longest_substring(s))  # Output: 3 (the longest substring without repeating characters is "abc")

public class LongestSubstring {

    public static int lengthOfLongestSubstring(String s) {
        int start = 0;
        int maxLength = 0;
        Map<Character, Integer> charIndexMap = new HashMap<>(); // HashMap to store the last index of each character in the string

        for (int i = 0; i < s.length(); i++) {
            if (charIndexMap.containsKey(s.charAt(i)) && charIndexMap.get(s.charAt(i)) >= start) {
                start = charIndexMap.get(s.charAt(i)) + 1;
            }
            charIndexMap.put(s.charAt(i), i);
            maxLength = Math.max(maxLength, i - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s)); // Output: 3 (the longest substring without repeating characters is "abc")
    }
}

function lengthOfLongestSubstring(s) {
    let start = 0;
    let maxLength = 0;
    const charIndexMap = new Map(); // Map to store the last index of each character in the string

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

    return maxLength;
}

// Test the function
const s = "abcabcbb";
console.log(lengthOfLongestSubstring(s)); // Output: 3 (the longest substring without repeating characters is "abc")

Notes ​

We will use a sliding window approach to solve this problem. The idea is to maintain a window of characters in the string such that all characters within the window are unique. We will keep track of the start index and end index of the window and use a data structure (HashMap/Dictionary) to store the last index of each character seen so far. As we move through the string, we will update the window and the data structure to maintain the uniqueness of characters within the window.

Algorithm: ​

1. Initialize two variables start and max_length to 0. These will keep track of the start index of the current window and the maximum length of the substring without repeating characters found so far.
2. Create an empty HashMap/Dictionary named char_index_map. This data structure will store the last index at which each character was seen in the string.
3. Iterate through the input string s using a loop and maintain an index variable i to traverse each character in the string.
4. Inside the loop, do the following: a. If the current character s[i] is present in the char_index_map, and its last index is greater than or equal to the start index, it means the character is repeating within the current window. In this case, update the start index to the next index after the last occurrence of the character. b. Update the char_index_map with the current character and its index, as we have seen it at position i. c. Update the max_length by taking the maximum of the current max_length and the length of the current window, i.e., i - start + 1.
5. Continue this process until all characters in the string have been processed.
6. The final max_length will be the length of the longest substring without repeating characters.