DEV Community

Cover image for Length of the longest substring without repeating characters
chandra penugonda
chandra penugonda

Posted on • Updated on

Length of the longest substring without repeating characters

This problem was asked by Yahoo.

You are given a string, find the length of the longest substring without repeating characters.

Example

function lengthOfLongestSubstring(string){

}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3
console.log(lengthOfLongestSubstring('bbbbb')); // 1
console.log(lengthOfLongestSubstring('pwwkew')); // 3
Enter fullscreen mode Exit fullscreen mode

Solution

function lengthOfLongestSubstring(str) {
  let start = 0;
  let longest = 0;
  const seen = {};
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}
Enter fullscreen mode Exit fullscreen mode

Explanation

  1. Initialize a seen object to track characters we've encountered before
  2. Initialize start to track the start of the current substring
  3. Iterate through each character in the string
  4. If we've seen this character before, update start to be the maximum of the current start or the last index for this character
  5. Update longest to be the max of itself or the current substring length
  6. Store the index + 1 of the current character in seen
  7. After iterating through all characters, longest will be the length of the longest substring without repeating characters.

Top comments (0)