3 Longest Substring Without Repeating Characters

Given a string, find the length of thelongest substringwithout repeating characters.

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.

Solution)

In the given string, remember any repeated character's position previously. Then, compare the current longest substring's length and the current and take the bigger one.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int lastRepeated = -1;
        int length = 0;
        int longest = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.get(c) != null && lastRepeated < map.get(c)) {
                lastRepeated = map.get(c);
            }
            longest = Math.max(longest, i - lastRepeated);
            map.put(c, i);
        }
        return longest;
    }
}