3. Longest Substring Without Repeating Characters

Description

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

Note: that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

Example 1

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2

Example 3

Solutions

Solution 1

/**
 * 
 * 
 */

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0, j = 0;
        Set<Character> set = new HashSet<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(set.contains(ch)) {
                while(j < i) {
                    if(s.charAt(j) == ch) {
                        j++;
                        break;
                    } else {
                        set.remove(s.charAt(j));
                        j++;
                    }
                }
            } else {
                set.add(ch);
                maxLen = Math.max(maxLen, set.size());
            }
        }
        return maxLen;
    }
}

Solution 2

Follow up