JavaScript Algorithm: Find the Longest Substring Without Repeating Characters (O(n) Time Complexity)

Problem Definition

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

Input: A single string s.

Output: An integer representing the length of the longest substring without repeating characters.

Constraints:

• 0 ≤ s.length ≤ 5 * 104
• The string s consists of English letters, digits, symbols, and spaces.

Example:

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

Understanding the Problem

The core challenge of this problem is to find the longest substring without repeating characters. This is significant in various applications such as data compression, pattern recognition, and more. A common pitfall is to overlook the need for an efficient solution, especially given the constraint that the string length can be up to 50,000 characters.

Approach

To solve this problem, we need to consider different approaches:

Naive Solution

The naive solution involves checking all possible substrings and determining if they have repeating characters. This approach is not optimal due to its high time complexity of O(n³).

Optimized Solution

A more efficient approach uses the sliding window technique with a hash map to keep track of characters and their positions. This allows us to achieve a linear time complexity of O(n).

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Initialize a hash map to store the last seen index of each character.
2. Use two pointers, left and right, to represent the current window of characters.
3. Iterate through the string with the right pointer.
4. If the character at right is already in the hash map and its index is within the current window, move the left pointer to the right of this character's last seen index.
5. Update the hash map with the current character's index.
6. Calculate the length of the current window and update the maximum length if necessary.

Code Implementation

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // Hash map to store the last seen index of each character
    let charIndexMap = new Map();
    // Initialize pointers and max length
    let left = 0, maxLength = 0;

    // Iterate through the string with the right pointer
    for (let right = 0; right < s.length; right++) {
        // If the character is already in the map and within the current window
        if (charIndexMap.has(s[right]) && charIndexMap.get(s[right]) >= left) {
            // Move the left pointer to the right of the last seen index
            left = charIndexMap.get(s[right]) + 1;
        }
        // Update the hash map with the current character's index
        charIndexMap.set(s[right], right);
        // Calculate the length of the current window
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

Complexity Analysis

The time complexity of the optimized solution is O(n) because each character is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set.

Edge Cases

Consider the following edge cases:

• Empty string: The output should be 0.
• String with all identical characters: The output should be 1.
• String with no repeating characters: The output should be the length of the string.

Examples:

Input: ""
Output: 0

Input: "aaaaa"
Output: 1

Input: "abcdef"
Output: 6

Testing

To test the solution comprehensively, consider using a variety of test cases:

• Simple cases with short strings.
• Edge cases such as empty strings and strings with all identical characters.
• Complex cases with long strings and mixed characters.

Example test cases:

console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3
console.log(lengthOfLongestSubstring("bbbbb")); // Output: 1
console.log(lengthOfLongestSubstring("pwwkew")); // Output: 3
console.log(lengthOfLongestSubstring("")); // Output: 0
console.log(lengthOfLongestSubstring("abcdef")); // Output: 6

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller parts and understand each part.
• Think about different approaches and their time complexities.
• Use diagrams or pseudo-code to visualize the solution.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find the longest substring without repeating characters using an optimized approach with a time complexity of O(n). Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills. Keep practicing and exploring further to master these concepts.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem
• GeeksforGeeks Article
• Coding Ninjas Problem