menu

### Longest Substring Without Repeating Characters

**Problem Statement:** Given a string s, find the length of the longest substring without repeating characters.

##
Examples

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

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

Input:s = "pwwkew"Output:3Explanation: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.

### Solutions

##
Brute Force Approach

##### Approach

This method involves using two loops: one to traverse the string and another nested loop to identify various substrings. Afterwards, the process involves systematically checking each substring. For every element within these substrings, we verify if it’s not present; if not, we store it in a HashSet. Conversely, if the element is found, we break from the loop and tally the count.

` ````
```class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0:
return 0
longest_length = -1
for i in range(len(s)):
char_set = {}
for j in range(i, len(s)):
if s[j] in char_set:
longest_length = max(longest_length, j - i)
break
char_set[s[j]] = 1
return longest_length

##### Time and Space Complexity

Time Complexity: O(N^{2})

Space Complexity: O(N) where N is the size of HashSet taken for storing the elements

##
Optimised Approach

##### Algorithm

Last seen

##### Intuition

We’ll create a map that keeps track of how many times each item appears. It’ll store the latest position of each item and count how often they show up.

##### Code

` ````
```class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
j = -1
lastSeen = {}
for i, c in enumerate(s):
j = max(j, lastSeen.get(c, -1))
ans = max(ans, i - j)
lastSeen[c] = i
return ans

##### Explanation

**Initialization:**`ans`

is initialized to 0, which will eventually hold the length of the longest substring without repeating characters.`j`

starts at -1, representing the last position of the character seen in the string.`lastSeen`

is a dictionary that keeps track of the last seen position of each character in the string.

**Loop through the String:**- The loop using
`enumerate()`

iterates through the string ‘s’, capturing both the index`i`

and character`c`

at each iteration.

- The loop using
**Updating the Last Seen Position:**- For each character
`c`

encountered in the string:`lastSeen.get(c, -1)`

retrieves the last seen position of character`c`

from the`lastSeen`

dictionary. If`c`

has not been seen before, it defaults to -1.`max(j, lastSeen.get(c, -1))`

ensures that`j`

is updated to the maximum of its current value and the last seen position of character`c`

. This step helps identify the starting index of the potential new substring without repeating characters.

- For each character
**Calculating the Length of Substring:**`i - j`

calculates the length of the current substring without repeating characters.`ans = max(ans, i - j)`

updates the`ans`

variable to store the maximum length found so far among all substrings without repeating characters.

**Updating Last Seen Position:**`lastSeen[c] = i`

updates the`lastSeen`

dictionary with the current index`i`

for the character`c`

. This step keeps track of the latest position of each character.

**Return:**- After the loop completes,
`ans`

holds the length of the longest substring without repeating characters, and it is returned as the final result.

- After the loop completes,

##### Time and Space Complexity

__Time Complexity:__ O(N)

__Space Complexity:__ O(N) where N represents the size of HashSet where we are storing our elements

WhatsApp

Facebook

Twitter

LinkedIn

Email