Longest Substring Without Repeating Characters: A String Traversal Challenge

The "Longest Substring Without Repeating Characters" problem is a common challenge in string processing, focusing on finding the longest unique substring in a given string.

Problem Statement

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

Example

• Input: "abcabcbb"
• Output: 3 (The answer is "abc", with the length of 3)

Solution Approach - Sliding Window Technique

function lengthOfLongestSubstring(s) {
  let map = new Map();
  let maxLen = 0,
    start = 0;

  for (let end = 0; end < s.length; end++) {
    if (map.has(s[end])) {
      start = Math.max(start, map.get(s[end]) + 1);
    }
    map.set(s[end], end);
    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
}

Breaking Down the Solution

• Sliding Window: Use two pointers (start and end) to create a sliding window that expands and contracts as it traverses the string.
• Track Characters: Use a map to track the last index of each character encountered.
• Adjust Window: When a repeated character is found, move the start pointer to avoid the repetition.
• Calculate Max Length: Continuously update the maximum length of the substring as the window slides.

Conclusion

The Longest Substring Without Repeating Characters problem is an excellent application of the sliding window technique in strings. It's commonly used in interview settings to assess understanding of string manipulation and efficient data storage.