Longest Substring Without Repeating Characters Algorithm

The Longest Substring Without Repeating Characters Algorithm is an efficient approach to find the length of the longest substring without any repeating characters within a given string. This algorithm is based on the sliding window technique, which maintains a window of characters within the string such that no character repeats. The algorithm iterates through the string, expanding the window by adding new characters to the right end, and shrinking the window by removing characters from the left end as needed to ensure that no repeating characters are present. The length of the longest substring without repeating characters is tracked throughout the iteration, ultimately providing the desired result. To implement this algorithm, a data structure such as a hash set or dictionary is used to store the characters within the current window and to check for the presence of repeating characters. As the algorithm iterates through the string, the data structure is updated to add new characters and remove old characters as appropriate, while also ensuring constant-time lookups for checking repetitions. The time complexity of this algorithm is O(n), as each character in the string is visited once, and the space complexity is O(min(m, n)), where m is the size of the character set and n is the length of the input string. This makes the Longest Substring Without Repeating Characters Algorithm an efficient and practical solution for this problem.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[256];
        for (int i = 0; i < 256; i++) {
            hash[i] = -1;
        }
        int maxlen = 0;
        int start = 0;
        for (int limit = 0; limit < s.size(); limit++) {
            if (hash[s[limit]] != -1) {
                start = max(start, hash[s[limit]] + 1);
            }
            maxlen = max(maxlen, limit - start + 1);
            hash[s[limit]] = limit;
        }
        return maxlen;
    }
};

LANGUAGE:

DARK MODE: