2. Longest Substring Without Repeating Characters

LC3

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

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.

Constraints:

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

Approach 1: Brute Force

Intuition

Check all the substring one by one to see if it has no duplicate character.

Implementation

class Solution {
    lengthOfLongestSubstring(s) {
        const n = s.length;

        let res = 0;
        for (let i = 0; i < n; i++) {
            for (let j = i; j < n; j++) {
                if (this.checkRepetition(s, i, j)) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }

        return res;
    }

    checkRepetition(s, start, end) {
        const chars = new Set();

        for (let i = start; i <= end; i++) {
            const c = s[i];
            if (chars.has(c)) {
                return false;
            }
            chars.add(c);
        }

        return true;
    }
}

// Example usage:
const solution = new Solution();
const result = solution.lengthOfLongestSubstring("abcabcbb");
console.log(result);

Complexity Analysis

Time complexity : O(n^3)

Approach 2: Sliding Window

Intuition

Given a substring with a fixed end index in the string, maintain a Set to record the element which have already occurred in the string.

• Use two pointers left and right and a variable len to store length
• Use Set to record visited characters s[right]
• Iterate over all the elements while right<s.length
• check if s[right] exists in set with st.has(s[right]
• if exists, move left++ and remove s[left] from set with st.delete(s[left])
• if doesn't exist increase len = max(len, right-left+1), add s[right] to set and increment right
• return len

Code

// JS Solution
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const st = new Set();
    let right = 0;
    let left = 0;
    let len = 0;
    while (right < s.length) {
      if (st.has(s[right])) {
        st.delete(s[left]);
        left++;
      } else {
        len = Math.max(len, right-left+1);
        st.add(s[right]);
        right++;
      }
    }
    return len;

};

Complexity Analysis

Time complexity : O(n^2)

Approach 3: Sliding Window Optimized

Intuition

Given a substring with a fixed end index in the string, maintain a HashMap to record the frequency of each character in the current substring. If any character occurs more than once, drop the leftmost characters until there are no duplicate characters.

Code

class Solution {
    lengthOfLongestSubstring(s) {
        const n = s.length;
        let res = 0;
        const mp = new Map();

        for (let j = 0, i = 0; j < n; j++) {
            if (mp.has(s[j]) && mp.get(s[j]) > 0) {
                i = Math.max(mp.get(s[j]), i);
            }
            res = Math.max(res, j - i + 1);
            mp.set(s[j], j + 1);
        }

        return res;
    }
}

// Example usage:
const solution = new Solution();
const result = solution.lengthOfLongestSubstring("abcabcbb");
console.log(result);

Complexity Analysis

Time complexity : O(n)

Space complexity : O(min(m,n)). Same as the previous approach.