Leetcode - Longest Substring Without Repeating Characters

Tags: leetcode two pointers set string

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

Complexity

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

---

comments powered by Disqus