Question

Formatted question description: https://leetcode.ca/all/3.html

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⁴
s consists of English letters, digits, symbols and spaces.

Algorithm

Given the example “abcabcbb,” the task is to find the longest substring without any repeating characters. This can be achieved by traversing the string character by character and maintaining a sliding window with no repeated characters. If a repeated character is encountered, the first occurrence of that character should be removed from the window.

To achieve this, we need to record the characters that have appeared before. One way to do this is to count the number of occurrences of each character. However, since the position of the character is important in this problem, we can use a HashMap to establish a mapping between each character and its last appearance position.

When considering how to record the character occurrences, we need to decide whether to save all occurrences or just record one location. The method we derived manually before is to maintain a sliding window with no repeated characters, and the size of the window needs to be enlarged as much as possible. Since the window is constantly sliding to the right, it only cares about the last position of each character and establishes a mapping.

To implement this approach, we can define a HashMap to create a mapping between each character and its last appearance position. We also need to define two variables, res and left, where res is used to record the length of the longest non-repeated substring, and left points to the previous starting position of the non-repeated substring on the left of the string. Since left is the previous position of the left border of the window, it is initialized to -1.

Next, we traverse the entire string character by character. For each character, if the character already exists in the HashMap and its mapping value is greater than left, we update left to the current mapping value. Then, we update the mapping value to the current coordinate i, which ensures that left is always the previous position of the current boundary. Finally, we update the result res with the length of the current window, which is i - left.

The condition m.count(s[i]) && m[s[i]] > left in the if statement in the program checks whether the current character s[i] has already been mapped in the HashMap. If so, it means that the character has already appeared before, and if m[s[i]] > left is true, it means that the previous occurrence of this character is in the current window. In this case, to add the current repeated character, we need to remove the previous occurrence. To do so, we assign left to m[s[i]], which is equivalent to moving the sliding window.

For example, when the string is “aa,” the mapping of a -> 0 is established when i = 0, and the result res is updated to 1. When i = 1, the character a is found in the HashMap, and the mapping value 0 is greater than -1 for left. Therefore, we update left to 0 and update the mapping pair to a -> 1. Then, i - left is still 1, so we don’t update the result res. The final result res is still 1, which is correct.

Code

import java.util.HashMap;


public class Longest_Substring_Without_Repeating_Characters {

    public static void main(String[] args) {

    	Longest_Substring_Without_Repeating_Characters out = new Longest_Substring_Without_Repeating_Characters();
        Solution s = out.new Solution();
        int longest = s.lengthOfLongestSubstring("abcbefg");

        System.out.println(longest);
    }

    // ref: https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/
    class Solution_map {
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }

            int result = 0;
            HashMap<Character, Integer> hm = new HashMap<>();

            for (int left = 0, right = 0; right < s.length(); right++) {
                char probeChar = s.charAt(right);
                if (hm.containsKey(probeChar)) {
                    // mast max check i
                    // example "abba", last 'a' will result in index 0 if not max checking
                    left = Math.max(left, hm.get(probeChar) + 1);
                }
                hm.put(probeChar, right);
                result = Math.max(result, right - left + 1);
            }

            return result;
        }
    }

    // @note: remove the final check outside while loop, cleaner code, run time: 7ms. above method 16ms
    /*
     * optimization is:
     * 1. moving longest recording after
     * 2. no extra operation: removing first repeated char in inner while, then adding this char to set next looping
     * 3. "Math.max(j - i + 1, maxLen)" is cleaner than "x>y ? x:y"
     *
     */
    class Solution {
        public int lengthOfLongestSubstring(String s) {

            if (s == null || s.length() == 0) {
                return 0;
            }

            int l = 0; // left
            int r = 0; // right

            int result = 0;
            boolean[] isFoundInWindow = new boolean[256];

            while (r < s.length()) {

                while (isFoundInWindow[s.charAt(r)]) {
                    isFoundInWindow[s.charAt(l)] = false;
                    l++;
                }

                isFoundInWindow[s.charAt(r)] = true;

                // check before shrink
                result = Math.max(result, r - l + 1);

                r++;
            }

            return result;
        }
    }

}

############

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> ss = new HashSet<>();
        int i = 0, ans = 0;
        for (int j = 0; j < s.length(); ++j) {
            char c = s.charAt(j);
            while (ss.contains(c)) {
                ss.remove(s.charAt(i++));
            }
            ss.add(c);
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/
// Time: O(N)
// Space: O(C) where C is the range of character set
// Ref: https://discuss.leetcode.com/topic/24739/c-code-in-9-lines
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, start = -1;
        vector<int> m(128, -1);
        for (int i = 0; i < s.size(); ++i) {
            start = max(start, m[s[i]]);
            m[s[i]] = i;
            ans = max(ans, i - start);
        }
        return ans;
    }
};

class Solution:
  def lengthOfLongestSubstring(self, s): # map for index
    d = {}
    start = 0
    ans = 0
    for i, c in enumerate(s):
      if c in d:
        # mast max check start, example "abba"
        start = max(start, d[c] + 1)
      d[c] = i
      ans = max(ans, i - start + 1)
    return ans


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if not s:
            return 0

        l = 0  # left
        r = 0  # right

        result = 0
        isFoundInWindow = [False] * 256

        while r < len(s):

            while isFoundInWindow[ord(s[r])]:
                isFoundInWindow[ord(s[l])] = False
                l += 1

            isFoundInWindow[ord(s[r])] = True

            # check before shrink
            result = max(result, r - l + 1)

            r += 1

        return result

class Solution: # extra space for set()
    def lengthOfLongestSubstring(self, s: str) -> int:

        d = collections.defaultdict(int)
        start = 0
        ans = 0
        for i,c in enumerate(s):
            # shrink
            while d[c] > 0:
                d[s[start]] -= 1 # not s[start], not start
                start += 1
            ans = max(ans, i - start + 1)
            d[c] = 1
        return ans

############

class Solution(object):
  def _lengthOfLongestSubstring(self, s): # no extra data structure
    """
    :type s: str
    :rtype: int
    """
    d = collections.defaultdict(int)
    l = ans = 0
    for i, c in enumerate(s):
      while l > 0 and d[c] > 0:
        d[s[i - l]] -= 1
        l -= 1
      d[c] += 1
      l += 1
      ans = max(ans, l)
    return ans

func lengthOfLongestSubstring(s string) int {
	ss := map[byte]bool{}
	i, ans := 0, 0
	for j := 0; j < len(s); j++ {
		for ss[s[j]] {
			ss[s[i]] = false
			i++
		}
		ss[s[j]] = true
		ans = max(ans, j-i+1)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function lengthOfLongestSubstring(s: string): number {
    const ss = new Set();
    let i = 0;
    let ans = 0;
    for (let j = 0; j < s.length; ++j) {
        while (ss.has(s[j])) {
            ss.delete(s[i++]);
        }
        ss.add(s[j]);
        ans = Math.max(ans, j - i + 1);
    }
    return ans;
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const ss = new Set();
    let i = 0;
    let ans = 0;
    for (let j = 0; j < s.length; ++j) {
        while (ss.has(s[j])) {
            ss.delete(s[i++]);
        }
        ss.add(s[j]);
        ans = Math.max(ans, j - i + 1);
    }
    return ans;
};

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        var ss = new HashSet<char>();
        int i = 0, ans = 0;
        for (int j = 0; j < s.Length; ++j)
        {
            while (ss.Contains(s[j]))
            {
                ss.Remove(s[i++]);
            }
            ss.Add(s[j]);
            ans = Math.Max(ans, j - i + 1);
        }
        return ans;
    }
}

proc lengthOfLongestSubstring(s: string): int =
  var
    i = 0
    j = 0
    res = 0
    literals: set[char] = {}

  while i < s.len:
    while s[i] in literals:
      if s[j] in literals:
        excl(literals, s[j])
      j += 1
    literals.incl(s[i]) # Uniform Function Call Syntax f(x) = x.f
    res = max(res, i - j + 1)
    i += 1

  result = res # result has the default return value

echo lengthOfLongestSubstring("abcddabcf")

use std::collections::HashSet;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let mut set = HashSet::new();
        let mut i = 0;
        s.iter()
            .map(|c| {
                while set.contains(&c) {
                    set.remove(&s[i]);
                    i += 1;
                }
                set.insert(c);
                set.len()
            })
            .max()
            .unwrap_or(0) as i32
    }
}

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var map = [Character: Int]()
        var currentStartingIndex = 0
        var i = 0
        var maxLength = 0
        for char in s {
            if map[char] != nil {
                if map[char]! >= currentStartingIndex {
                    maxLength = max(maxLength, i - currentStartingIndex)
                    currentStartingIndex = map[char]! + 1
                }
            }
            map[char] = i
            i += 1
        }
        return max(maxLength, i - currentStartingIndex)
    }
}

3 - Longest Substring Without Repeating Characters

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions