LeetCode 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Difficulty: Medium

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.

Solution

Language: Java

用队列作为窗口

class Solution {
      public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                  return 0;
           }
            Map<Character, Integer> map = new HashMap<>();
            Queue<Character> q = new LinkedList<>();
            int l = s.length();
            int max = 0;
            for (int i = 0; i < l; i++) {
                  char c = s.charAt(i);
                  if (map.containsKey(c)) {
                        if (q.size() > max) {
                              max = q.size();
                       }
                        while(!q.isEmpty()) {
                              char a = q.poll();
                              map.remove(a);
                              if (a == c) {
                                    break;
                             }
                       }
                 }
                  q.offer(c);
                  map.put(c, i);
           }
            return q.size() > max ? q.size() : max;
     }
}

官方答案

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

记录最后一个重复的位置，在那之前的记录的位置视为无效

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] pos = new int[256];
        Arrays.fill(pos, -1);
        int maxLen = 0;
        int len = 0;
        int lastPos = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (pos[c] == -1 || pos[c] < lastPos) {
                len++;
                maxLen = Math.max(maxLen, len);
                pos[c] = i;
            } else{
                lastPos = pos[c] + 1;
                len = i - pos[c];
                maxLen = Math.max(maxLen, len);
                pos[c] = i;
            }
        }
        return Math.max(len, maxLen);
    }
}