LeetCode Problem Link

https://leetcode.com/problems/longest-substring-without-repeating-characters

Intuition

• use two-pointers for implementing a sliding window and a hash table for checking previous occurrences

        std::unordered_set<char> hash;
        for (size_t r=0; r<n; ++r) {
            auto it = hash.find(s[r]);
            if (it == end(hash)) {
                hash.emplace(s[r]);
                max_len = std::max(max_len, (r+1)-l);
            }
            else {
                while (l<=r && s[l] != s[r]) {
                    hash.erase(s[l++]);
                }
                ++l;
            }
        }
  

Approach

• unordered_set is too expensive for processing ‘char’ type => use 256 sized array

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    int lengthOfLongestSubstring(string s) {
        const size_t n = s.length();
        size_t max_len = 0;
        std::array<int32_t, 256> pos;
        pos.fill(-1);
        size_t l=0;
        for (size_t r=0; r<n; ++r) {
            const uint8_t s_r = static_cast<uint8_t>(s[r]);
            if (pos[s_r] < static_cast<int32_t>(l)) {
                max_len = std::max(max_len, (r+1)-l);
            }
            else {  // if it exists
                l = std::max(l, static_cast<size_t>(pos[s_r])+1);
            }
            pos[s_r] = static_cast<int32_t>(r);
        }
        return max_len;
    }

GitHub

• ToDo: longest-substring-without-repeating-characters