0003 - Longest Substring Without Repeating Characters

0003 - Longest Substring Without Repeating Characters

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

Examples

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

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

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.

Input: s = "" Output: 0

Constraints

0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces.

Java Solution

Dynamic Programming (Sliding Window)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        
        Map<Character, Integer> hm = new HashMap<>(); // <char, index>
        int p1 = 0;
        for(int p2 = 0; p2 < s.length(); p2++) {
            if(hm.containsKey(s.charAt(p2))) p1 = Math.max(hm.get(s.charAt(p2)), p1);
            max = Math.max(max, p2-p1+1);
            hm.put(s.charAt(p2), p2+1);
        }
        return max;
    }
}