Longest Substring Without Repeating Characters medium

Problem Statement

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

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.

Steps:

1. Initialization: Use a unordered_map (or HashMap in Java) to store the characters and their last seen indices. Initialize a maxLength variable to 0, which will store the length of the longest substring without repeating characters. Initialize start and end pointers to 0.

2. Sliding Window: Iterate through the string using the end pointer.

3. Character Check: For each character at index end:

   • If the character is not in the unordered_map (or its last seen index is less than start), it means it's a new character. Update its index in the unordered_map and update maxLength if the current substring length (end - start + 1) is greater.
   • If the character is already in the unordered_map and its last seen index is greater than or equal to start, it means there's a repetition. Move the start pointer to the next position after the previous occurrence of this character. Update the character's index in the unordered_map.

4. Return: After iterating through the entire string, return maxLength.

Explanation:

The solution employs a sliding window technique. The window represents a substring. We expand the window by moving the end pointer. If a repeating character is encountered, we shrink the window from the left by moving the start pointer to eliminate the repetition. The unordered_map efficiently tracks the last seen index of each character, allowing for quick lookups.

Code:

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charIndexMap;
    int maxLength = 0;
    int start = 0;
    int end = 0;

    while (end < s.length()) {
        char currentChar = s[end];
        if (charIndexMap.find(currentChar) == charIndexMap.end() || charIndexMap[currentChar] < start) {
            maxLength = max(maxLength, end - start + 1);
            charIndexMap[currentChar] = end;
            end++;
        } else {
            start = charIndexMap[currentChar] + 1;
            charIndexMap[currentChar] = end;
            end++;
        }
    }

    return maxLength;
}

int main() {
    string s1 = "abcabcbb";
    string s2 = "bbbbb";
    string s3 = "pwwkew";
    cout << "Length of longest substring without repeating characters in '" << s1 << "': " << lengthOfLongestSubstring(s1) << endl; // Output: 3
    cout << "Length of longest substring without repeating characters in '" << s2 << "': " << lengthOfLongestSubstring(s2) << endl; // Output: 1
    cout << "Length of longest substring without repeating characters in '" << s3 << "': " << lengthOfLongestSubstring(s3) << endl; // Output: 3
    return 0;
}

Complexity:

• Time Complexity: O(n), where n is the length of the string. In the worst case, we iterate through the string once.
• Space Complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set. In the worst case, the unordered_map could store all unique characters from the string. If the string contains all unique characters, space complexity would be O(n). If the character set is smaller than the string length (e.g., ASCII characters), the space complexity would be O(m).