48. The longest substring without repeating characters

Find the longest substring from the string that does not contain repeated characters, and calculate the length of the oldest string.

Example 1:

Input: “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1. Example 3:

Input: “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wke”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

1, the linked list

Given the first-in, first-out nature of string validation, a linked list approach is preferable

public int lengthOfLongestSubstring(String s) {

    if (s == null || s.length() == 0) {return 0;
    }

    int totalLength = s.length();
    int maxSize = 0;

    Queue <Character>queue = new LinkedList<Character>();

    for (int i = 0; i < totalLength; i++) {
        char c = s.charAt(i);

        while (queue.contains(c)){
            queue.poll();
        }
        queue.add(c);
        maxSize = Math.max(maxSize,queue.size());
    }

    return maxSize;
}
Copy the code