Longest Substring Without Repeating Characters

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

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

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

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.

Solutions

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(N2)

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

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
  1. Initialization:
    1. ans is initialized to 0, which will eventually hold the length of the longest substring without repeating characters.
    2. j starts at -1, representing the last position of the character seen in the string.
    3. lastSeen is a dictionary that keeps track of the last seen position of each character in the string.
  2. Loop through the String:
    1. The loop using enumerate() iterates through the string ‘s’, capturing both the index i and character c at each iteration.
  3. Updating the Last Seen Position:
    1. For each character c encountered in the string:
      1. 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.
      2. 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.
  4. Calculating the Length of Substring:
    1. i - j calculates the length of the current substring without repeating characters.
    2. ans = max(ans, i - j) updates the ans variable to store the maximum length found so far among all substrings without repeating characters.
  5. Updating Last Seen Position:
    1. 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.
  6. Return:
    1. After the loop completes, ans holds the length of the longest substring without repeating characters, and it is returned as the final result.
 
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

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.