0003 - Longest Substring Without Repeating Characters (Medium)

Problem Link

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

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.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Approach 1: HashSet with One Iteration

Two pointer i and j, initially at the start of the string. Move right (j++) till distinct characters and store them in set. If repeated character occurs then move left (i++) until that repeated character is occured in left, and also remove all characters that occur before that character including character itself from set. This helps to maintain Set with longest substring.

Time complexity: $O(n)$, where $n$ - # of characters in the string

Space complexity: $O(s)$, where $s$ is the longest substring

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int i = 0, j = 0, max = 0;
        Set<Character> seen = new HashSet<>();
        while (j < s.length()) {
            if (seen.add(s.charAt(j))) {
                max = Math.max(max, seen.size());
                j += 1;
            } else {
                seen.remove(s.charAt(i++));
            }
        }
        return max;
    }
}

Approach 2: Sliding Window with ASCII

We can solve this problem with Sliding Window and Two pointers i and j. Iterate over the string, keep moving the 2nd pointer j forward until the character is not matched with i th character.

Since the input, may contain English letters, digits, symbols and spaces, so maintain the ASCII char array of size 128.

If any of the character occur more than once, then break the loop and find the difference of j and i and that's the longest substring length.

Time complexity: $O(n)$, where $n$ - # of characters in the string. Since both i and j moving in one direction and it's total is $O(2n)$, constants are ignored, so it's $O(n)$.

Space complexity: $O(1)$ extra space, size of 128 ASCII chars for each iteration, considered as constant space.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        if (s.length() == 1) return 1;
        int max = 0;
        for (int idx = 0; idx < s.length() - 1; idx++) {
            int[] seen = new int[128];
            int i = idx, j = idx + 1;
            while (j < s.length() && s.charAt(i) != s.charAt(j)) {
                if (seen[s.charAt(j)] > 0) break;
                seen[s.charAt(j)]++;
                j++;
            }
            max = Math.max(max, j - i);
        }
        return max;
    }
}