Recover Tree From Preorder in JavaScript

Longest Substring Without Repeating Characters - JavaScript Solution with 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 * 10⁴
The string s consists of English letters, digits, symbols, and spaces.

Example:

Input: s = "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 in a given string that does not contain any repeating characters. This problem is significant in various applications such as data validation, parsing, and text processing. A common pitfall is to overlook the need to update the starting point of the substring when a repeating character is found.

Approach

To solve this problem, we can use a sliding window technique. The idea is to use two pointers to represent the current window of characters being considered. We expand the window by moving the right pointer and check if the character is already in the current window. If it is, we move the left pointer to the right of the first occurrence of the repeating character. This ensures that the window always contains unique characters.

Let's discuss a naive solution first:

Naive Solution

The naive approach is to generate all possible substrings and check each one for unique characters. This approach is not optimal because it has a time complexity of O(n³), where n is the length of the string. This is due to the nested loops required to generate substrings and the additional loop to check for uniqueness.

Optimized Solution

The optimized solution uses the sliding window technique with a hash map to store the characters and their indices. This allows us to efficiently check for repeating characters and update the window accordingly. The time complexity of this approach is O(n), where n is the length of the string, because each character is processed at most twice.

Algorithm

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

Initialize a hash map to store the characters and their indices.
Initialize two pointers, left and right, both set to 0.
Initialize a variable maxLength to store the length of the longest substring found.
Iterate through the string using the right pointer.
For each character, check if it is already in the hash map and its index is within the current window.
If it is, update the left pointer to the right of the first occurrence of the repeating character.
Update the hash map with the current character and its index.
Update maxLength with the length of the current window if it is larger than the previous maximum.
Return maxLength after the loop ends.

Code Implementation

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // Hash map to store the characters and their indices
    let charIndexMap = new Map();
    // Initialize pointers and maxLength
    let left = 0, right = 0, maxLength = 0;

    // Iterate through the string
    while (right < s.length) {
        // Get the current character
        let currentChar = s[right];

        // Check if the character is in the map and within the current window
        if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
            // Update the left pointer
            left = charIndexMap.get(currentChar) + 1;
        }

        // Update the map with the current character and its index
        charIndexMap.set(currentChar, right);

        // Update maxLength if the current window is larger
        maxLength = Math.max(maxLength, right - left + 1);

        // Move the right pointer
        right++;
    }

    // Return the length of the longest substring
    return maxLength;
};

Complexity Analysis

The time complexity of the optimized solution is O(n), where n is the length of the string. This is 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 m is the size of the character set, because the hash map stores at most m characters.

Edge Cases

Here are some potential edge cases and how the algorithm handles them:

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

Examples:

Input: s = ""
Output: 0

Input: s = "abcdef"
Output: 6

Input: s = "aaaaaa"
Output: 1

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple cases with short strings.
Cases with mixed characters (letters, digits, symbols).
Edge cases such as empty strings and strings with all identical 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, it is important to:

Understand the problem requirements and constraints thoroughly.
Consider different approaches and their trade-offs.
Break down the problem into smaller, manageable parts.
Use diagrams or pseudo-code to visualize the solution.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the longest substring without repeating characters using JavaScript. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews. Keep practicing and exploring further to master these concepts.