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

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.

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

/**
 * Time complexity : O(n). Index j will iterate n times.
 * 
 */

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0, n = s.length();
        int[] index = new int[128];
        Arrays.fill(index, -1);
        for(int j = 0, i = 0; j < n; j++) {
            char ch = s.charAt(j);
            i = Math.max(i, index[ch]);
            maxLen = Math.max(maxLen, j-i+1);
            index[ch] = j+1;
        }
        return maxLen;
    }
}

Follow up