life is too short for a diary




Tue 18 Jan 2022

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

Longest substring image

Solution

Complexity

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


comments powered by Disqus