Strings - Question 5 Longest Substring Without Repeating Characters (Medium)

Question

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

Verify the constraints

1. Is the substring contiguous? - Yes, look for a substring not a subsequence.
2. Does case sensitivity matter? - No, assume all characters in the string are lowercase.

Write out some test cases

1. "abccabb" - 3
2. "cccccccc" - 1
3. "" - 0
4. "abcbda" - 4
5. "abcbdca" - 4

Figure out a solution without code

1. start from the 0 index, pointer goes forward and save the letter in the object (letter : index) until it meets the same letter
2. if it meets the same letter, then pointer goes backward to the same previous letter index + 1
3. start from that index and repeat this process all over again
4. while doing this, save the max value in the max varient

Write out our solution in code

Solution 1

function longestSubstrWithoutRepeatingChar(str){
    let i = 0;
    let charObj = {};
    let max = 0;
	while(i < str.length){
	    if(!charObj[str[i]]){
	        charObj[str[i]] = i;
	        i++;
          }else{
            let len = Object.keys(charObj).length;
            if(max < len){
                max = len;
            }
            let prevRepeatedCharIndex = charObj[str[i]];
            i = prevRepeatedCharIndex + 1;
           charObj = {}
        }
    }
  let len = Object.keys(charObj).length;
  if(max < len){
    max = len;
  }
    return max;
}

console.log(longestSubstrWithoutRepeatingChar("abccabb"))
console.log(longestSubstrWithoutRepeatingChar("ccccccccc"))
console.log(longestSubstrWithoutRepeatingChar(""))
console.log(longestSubstrWithoutRepeatingChar("abcbda"))
console.log(longestSubstrWithoutRepeatingChar("abcbdca"))
console.log(longestSubstrWithoutRepeatingChar("abcdefbaghghijklm"))

Sliding Window Technique!

Form a window over some portion of sequential data, then move that window throughout the data to capture different parts of it! Move window like below

Solution 2

I used sliding window technique right out of my head, but this solution 2 is more optimized one!

• Use a sliding window to represent the current substring.
• The size of the window will change based on new characters, and characters we've seen before.
• Our seen characters hashmap keeps track of what characters we've seen and the index we saw them at.

function longestSubstrWithoutRepeatingChar(str){
  let L = 0;
  let R = 0;
  let charObj = {};
  let max = 0;
  while(R < str.length){
    if(charObj[str[R]] >= L){
      L = charObj[str[R]]+1;
    }
    charObj[str[R]] = R;
    let len = R - L + 1;
      if(max < len){
        max = len;
      }
      R++;
  }
  return max;
}

console.log(longestSubstrWithoutRepeatingChar("abccabb"))
console.log(longestSubstrWithoutRepeatingChar("ccccccccc"))
console.log(longestSubstrWithoutRepeatingChar(""))
console.log(longestSubstrWithoutRepeatingChar("abcbda"))
console.log(longestSubstrWithoutRepeatingChar("abcbdca"))
console.log(longestSubstrWithoutRepeatingChar("abcdefbaghghijklm"))

Analyze Space and Time Complexity

• Solution 1
  • Time Complexity : O(N)
  • Space Complexity : O(N)
• Solution 2
  • Time Complexity : O(N)
  • Space Complexity : O(N)

Leetcode Optimal Code

if you use new Map(), runtime and memory usage is go way up.

Developing References

Developing Report

2025-01-22 - Strings - Question 5 Longest Substring Without Repeating Characters (Medium) Report
2025-01-22 - Developing Daily Report
2025-01-4th - Developing Weekly Report