Leetcode - Longest Substring Without Repeating Characters

Tags: leetcode two pointers set

In this leetcode problem, we are asked to find the length of the longest string of characters in a provided string that does not contain repeating characters. In other words, in the string abcabcbb the longest substring without repeating characters is abc (with a length of 3).

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.

Explanation

We can use two pointers to solve this problem.

1. Assign i = 0 and left = 0.

2. Create a set to keep track of characters in the substring.

3. Loop through the string

• If the character at index i is not in the set, we add it to the set and increment i pointer.

• If the character at index i is in the set, then we have found a new substring. We remove the character at index left from the set and increment left pointer.

Solution

• Java
• Python

	class Solution {
	public int lengthOfLongestSubstring(String s) {
	if (s.isEmpty()){
	return 0;
	}
	if (s.length() == 1){
	return 1;
	}
	Set<Character> track = new HashSet<>();
	int i = 0, left = 0, maxCount = 0;
	while (i < s.length()){
	char current = s.charAt(i);
	if (!track.contains(current)){
	i++;
	track.add(current);
	} else{
	maxCount = Math.max(maxCount, track.size());
	track.remove(s.charAt(left));
	left++;
	}
	}
	return Math.max(maxCount, track.size());
	}

view raw LengthOfLongestSubstring.java hosted with ❤ by GitHub

	class Solution:
	def lengthOfLongestSubstring(self, s: str) -> int:
	if len(s) == 0:
	return 0
	if len(s) == 1:
	return 1
	max_count, left = 0, 0
	track = set()
	i = 0
	while i < len(s):
	if s[i] not in track:
	track.add(s[i])
	i = i + 1
	else:
	max_count = max(max_count, len(track))
	track.remove(s[left])
	left = left + 1
	return max(max_count, len(track))

view raw length_of_longest_substring.py hosted with ❤ by GitHub

Complexity

Time Complexity is $$\mathcal{O}(n)$$, Space complexity is $$\mathcal{O}(1)$$

---

comments powered by Disqus