LeetCode Problem: "Longest Substring Without Repeating Characters"

 LeetCode Problem and solution in Javascript

 
 

Objective: 

In this challenge, we will solve the “Longest Substring Without Repeating Characters” LeetCode puzzle using javascript. 

Problem statement: 

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

It must return the display text as shown in the examples: 

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Note:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

Solution Approach 1: Brute Force:

var lengthOfLongestSubstring = function(s) {

    var strArr= s.split('')

    if (strArr.length==0) return 0;

    if (strArr.length==1) return 1;

    

    let max=0;

    let str='';

    var n = strArr.length

    for(var i=0;i<n; i++){

        var substring=strArr[i]

        for(var j=i+1;j<n; j++){

          if(!substring.includes(strArr[j])){

              substring=substring+strArr[j]

             max= Math.max(max,substring.length)

              

          }

            else{

                 max= Math.max(max,substring.length)

                 break;

            }

         

        }   

    }

    return max

};

Solution Approach 2 : Sliding Window:

var lengthOfLongestSubstring = function(s) {

    if (s.length==0) return 0;

    if (s.length==1) return 1;

    

    let max=0;

    // seenchars will store the char as key and index as value

    let seenChars=new Map();

    var n = s.length

    //sliding window 

    var left =0;

    for(let right=0;right<n; right++){

        let currentChar=s[right]

     

            let prevSeenCharIndex= seenChars.get(currentChar)

            if(prevSeenCharIndex>=left){

                left=prevSeenCharIndex+1

            }

        

        seenChars.set(currentChar,right)

       // console.log(seenChars)

        max= Math.max(max,right-left+1)   

    }

    return max

};