## Wednesday, November 30, 2022

### 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;    }}`

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS