Easy_Question26 : find the length of the longest substring without repeating characters.

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 consists of English letters, digits, symbols and spaces.

Approach 1 Sliding Window

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.

Algorithm

• The naive approach is very straightforward. But it is too slow. So how can we optimize it?

• In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring sijs_{ij}s ij 

• By using HashSet as a sliding window, checking if a character in the current can be done in O(1)O(1)O(1).

import java.util.*; 
public class Solution {
   
   public static void main(String[] args){
      System.out.println("lengthOfLongestSubstring "+ lengthOfLongestSubstring("abcabcbb"));
   }
   public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> chars = new HashMap();
        int left = 0;
        int right = 0;
        int res = 0;
        while (right < s.length()) {
            char r = s.charAt(right);
            chars.put(r, chars.getOrDefault(r,0) + 1);
            
            while (chars.get(r) > 1) {
                char l = s.charAt(left);
                chars.put(l, chars.get(l) - 1);
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }
}

Approach 2 Sliding Window Optimized

Intuition

• The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

import java.util.*; 
public class Solution {
   
   public static void main(String[] args){
      System.out.println("lengthOfLongestSubstring "+ lengthOfLongestSubstring("abcabcbb"));
   }
   public static int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}