Find the Longest Substring Without Repeating Characters: Solution and Algorithm

The problem of finding the longest substring without repeating characters is a common problem in computer science and can be found in various coding interviews and competitions. The task is to find the longest substring in a given string that does not contain any repeating characters.

For example, given the string “abcabcbb”, the longest substring without repeating characters would be “abc”, with a length of 3. Similarly, given the string “bbbbb” the longest substring without repeating characters would be “b”, with a length of 1.

Approach 1:

There are several ways to solve this problem. One common approach is to use a sliding window algorithm. This approach involves maintaining a window of characters and moving the window through the input string while keeping track of the characters in the window. If a repeating character is found, the window is moved to the right and the character is removed from the window. The length of the window is updated if a longer substring is found.

Here is a sample Python implementation of the sliding window approach:

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    max_length = 0
    i = 0
    j = 0
    while (j < len(s)):
        if s[j] not in char_set:
            char_set.add(s[j])
            j += 1
            max_length = max(max_length, j - i)
        else:
            char_set.remove(s[i])
            i += 1
    return max_length

Approach 2:

Another approach is to use a hashmap to keep track of the last seen index of each character in the input string. The key idea behind this algorithm is to use a hashmap to keep track of the last seen index of each character in the input string. The variable “start “keeps track of the starting index of the current substring, and the variable “max_length “keeps track of the maximum length of substring seen so far.

The hashmap approach to solving the problem of finding the longest substring without repeating characters is based on the idea of using a hashmap to keep track of the last seen index of each character in the input string. By maintaining a record of the last seen index of each character, we can easily determine if a given character is a repeat, and if so, where the last occurrence of that character was in the input string.

Here’s how the algorithm works:

1. Initialize a variable start to keep track of the starting index of the current substring, and a variable “max_length” to keep track of the maximum length of substring seen so far.
2. Create an empty hashmap to store the last seen index of each character in the input string.
3. Iterate through the input string one character at a time.
4. For each character, check if it has been seen before. If it has, update the start variable to be one greater than the last seen index of that character.
5. Update the “max_length“ variable to be the maximum of the current “max_length “and the difference between the current index and the start variable.
6. Store the current index in the hashmap for the current character.
7. Return the value of ‘max_length ‘as the final result.

Here is a sample C++ implementation of this approach:

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> char_map;
    int max_length = 0;
    int start = 0;
    for (int i = 0; i < s.size(); i++) {
        if (char_map.count(s[i]) && char_map[s[i]] >= start) {
            max_length = max(max_length, i - start);
            start = char_map[s[i]] + 1;
        }
        char_map[s[i]] = i;
    }
    return max(max_length, (int)s.size() - start);
}

The time complexity of this approach is O(n) and the space complexity is O(min(n, m)) where n is the length of the input string and m is the size of the character set.

Approach 3:

Another approach to solve the problem of finding the longest substring without repeating characters is to use two pointers. This approach uses two pointers, one to traverse the input string and the other to keep track of the substring without repeating characters.

The idea behind this approach is to use one pointer, called “start”, to mark the start of the current substring, and another pointer, called “end”, to traverse the input string. As we traverse the input string, we use a hashmap to keep track of the last seen index of each character. If we encounter a character that has been seen before, we update the “start” pointer to be the last seen index of that character plus one. We then update the maximum length of the substring without repeating characters if the current substring is longer than the previous maximum.

Here is a sample C++ implementation of this approach:

int lengthOfLongestSubstring(string s) {
    int start = 0, max_length = 0;
    unordered_map<char, int> char_map;
    for (int end = 0; end < s.size(); end++) {
        if (char_map.count(s[end]) && char_map[s[end]] >= start) {
            start = char_map[s[end]] + 1;
        }
        char_map[s[end]] = end;
        max_length = max(max_length, end - start + 1);
    }
    return max_length;
}

This solution has a time complexity of O(n) and space complexity of O(min(n, m)), where n is the length of the input string and m is the size of the character set.

The two pointer approach is efficient in the sense that it only iterates through the input string once, thus having a linear time complexity. This approach is also relatively simple to understand and implement, making it a popular choice among interviewers and competitive programmers.