3.Longest-Substring-Without-Repeating-Characters

3. Longest Substring Without Repeating Characters

题目地址

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目描述

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

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

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

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

代码

Approach 1: Sliding Window

Complexity Analysis

• Time complexity : O(2n)

• Space complexity : O(min(m, n))

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int ans = 0, i = 0, j = 0;
    while (i < n && j < n) {
      if (!set.contains(s.charAt(j))) {
        set.add(s.charAt(j++));
        ans = Math.max(ans, j - i);
      } else {
        set.remove(s.charAt(i++));
      }
    }

    return ans;
  }
}

Approach 2: Sliding Window Optimized

map: Character => Index

conatians character => update i

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();

    for (int j = 0, i = 0; j < n; j++) {
      if (map.containsKey(s.charAt(j))) {
        i = Math.max(map.get(s.charAt(j)) + 1, i);
      }
      ans = Math.max(ans, j - i + 1);
      map.put(s.charAt(j), j); 
    }

    return ans;
  }
}

用 int[128] 代替 map: Character => index

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length(), ans = 0;
    int[] index = new int[128];
    for (int j = 0, i = 0; j < n; j++) { abbcde
      i = Math.max(index[s.charAt(j)], i);
      ans = Math.max(ans, j - i + 1);
      index[s.charAt(j)] = j + 1; // 为什么 j+1 => 当遇到i元素去重后, 取下一位
    }

    return ans;
  }
}

Approach 3: Brute Force

Intuition

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

Complexity

• Time complexity: O(n^3)

• Space complexity: O(min(n,m)), The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

class Solution {
    public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; i <= n; j++) {
        if (allUnique(s, i, j)) {
          ans = Math.max(ans, j - i);
        }
      }
    }

    return ans;
  }

  public boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i < end; i++) {
      Character ch = s.charAt(i);
      if (set.contains(ch)) return false;
      set.add(ch);
    }
    return true;
  }

}