Longest Substring Without Repeating Characters

Link

Description

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

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

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

Example 2:

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

Example 3:

• 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.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Solution

Way 1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        unordered_map<char, int> mapping;
        for (int left = 0, right = 0; right < s.length(); right++) {
            mapping[s[right]]++;
            while (mapping[s[right]] > 1) {
                mapping[s[left]]--;
                left++;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

Explanation:

1. Initialization: The solution initializes a result variable res to store the maximum length of substrings without repeating characters found so far. It also declares an unordered_map<char, int> named mapping to keep count of the characters within the current window.
2. Sliding Window with Character Count: The solution iterates through the string with two pointers, left and right, representing the start and end of the current window, respectively. For each character at position right, it increments its count in mapping.
3. Handling Repeats: If the count of the current character exceeds 1 (meaning the character is repeated within the current window), the loop reduces the count of the character at the left pointer and moves left forward until the current character's count is 1 again. This effectively shrinks the window from the left side to remove the repeating character.
4. Updating the Maximum Length: After ensuring there are no repeating characters in the current window, the solution updates res with the maximum length of the current window (right - left + 1).

5. Result: Once the entire string has been processed, the maximum length stored in res is returned.

6. Time Complexity: \(O(2n)\approx O(n)\);

7. Space Complexity: \(O(\min (n, m))\).

Way 2

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        vector<int> last(256, -1);
        int res = 0;
        for (int left = 0, right = 0; right < n; right++) {
            left = max(left, last[s[right]] + 1);
            res = max(res, right - left + 1);
            last[s[right]] = right;
        }
        return res;
    }
};

Another way of writing (with hash map):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Hash map to store the last occurrence of characters
        unordered_map<char, int> last;
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            if (last.find(s[right]) != last.end()) {
                // Update the start of the window, if necessary
                left = max(left, last[s[right]] + 1);
            }
            // Update the maximum length found
            res = max(res, right - left + 1);
            // Update the last occurrence of the current character
            last[s[right]] = right;
        }
        return res;
    }
};

Explanation:

In our solution, the unordered_map<char, int> named last serves as the cornerstone, mapping each character to its last occurrence's index in the string. This map is updated and queried as we expand and shift our sliding window:

1. Initialization: An empty unordered_map is created to store characters and their last seen index. No pre-allocation or assumption about the character set size is necessary, making our solution adaptable and memory efficient.
2. Iterating Through the String: We iterate through the string with two pointers, marking the current window's start and end. For each character, we perform a lookup in our map to decide if the window needs adjustment.
3. Adjusting the Window: If a character has been seen previously within the current window, we move the window's start just beyond the character's last occurrence. This step ensures our window always contains unique characters.
4. Updating the Maximum Length: We continually update our maximum length found as we adjust the window, ensuring we capture the longest possible substring without repeats.
5. Updating last: For each character processed, we update its last seen index in our unordered_map, readying it for future window adjustments.

Certainly! Analyzing the time and space complexity of the solution using unordered_map for the problem of finding the longest substring without repeating characters is crucial for understanding its efficiency and scalability. Let's break down both aspects:

Time Complexity:

The time complexity of this solution primarily depends on the length of the input string and the operations performed for each character in the string.

1. Traversal: The algorithm traverses the input string once. During each iteration, it performs a few key operations: checking if a character is in the unordered_map, updating the start of the window, calculating the maximum length so far, and updating the unordered_map with the current character's last occurrence.
2. Map Operations: The operations on the unordered_map, including insertion (updating the last occurrence of a character) and lookup (checking if a character is already in the map), have an average time complexity of \(O(1)\). However, in the worst-case scenario, these operations can degrade to \(O(n)\), where \(n\) is the number of characters in the string. This degradation is rare and usually mitigated by the hash function used in the unordered_map.

Considering the average case, where map operations are \(O(1)\), the overall time complexity of the algorithm is \(O(n)\), where n is the length of the input string.

Space Complexity:

The space complexity of the solution is influenced by the data structures used to track the characters and their last occurrences.

1. unordered_map Storage: The unordered_map holds a key-value pair for each unique character that appears in the string. In the worst-case scenario, where all characters in the string are unique, the size of the map grows linearly with the number of characters, \(n\).
2. Character Set Consideration: The maximum size of the unordered_map is also bounded by the size of the character set used in the input string. For example, if the string only contains ASCII characters, the maximum number of unique keys in the map would be \(256\). However, for a Unicode string, this could be much larger.

Given that the space required by the unordered_map depends on the number of unique characters, the worst-case space complexity is \(O(\min (n, m))\), where \(n\) is the length of the string and \(m\) is the size of the character set. This complexity reflects the storage needed for the map in the scenario of either all characters being unique or the total size of the character set, whichever is smaller.