Longest substring without repeating characters python

LeetCode Longest Substring Without Repetition Solution in Python

LeetCode is a platform that gives access to numerous coding problems that are usually asked in technical interviews of tech giants such as Google, Meta and Amazon for Engineering and Machine Learning positions.

In today’s article, we are going to explore a couple of approaches for the third problem on LeetCode problem which is of medium difficulty level and is called “Longest substring without repetition”.

The Problem

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.

Input: s = ""
Output: 0

Constraints:

A brute force approach

The most intuitive approach to the problem would be to perform a brute force search by using two nested loops.

class Solution: 
def lengthOfLongestSubstring(self, s: str) -> int: 
 
longest_str = "" 
for i, c in enumerate(s): 
canditate_str = str(c) 
for j in range(i + 1, len(s)): 
if s[j] not in canditate_str: 
canditate_str += str(s[j]) 
else: 
break 
if len(canditate_str) > len(longest_str): 
longest_str = canditate_str

Источник

LeetCode #3 — Longest Substring Without Repeating Characters

Hey happy folks 👋! It’s a brand new day and it’s time to look at another problem from LeetCode — Longest Substring Without Repeating Characters.

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.

The input will be a string containing characters which may or may not be repeated. The ask is to find the longest substring (a part of the given string) having all distinct characters.

One characteristic of a substring is that all the characters are contiguous. For e.g, in a given string s = redquark , the valid substrings are — edq , ar , red , quar etc. The substrings rd , qur are not valid substrings because even though they contain characters from the source strings, those characters are not continuous.

Apart from above, we are given constraints on the size of string and the characters that are present in a string.

There can be many substrings as outputs but we have to return only the longest among them.

From the input, we can gather the following information —

1. Given data structure is a string which is a linear data structure.
2. The output must be a substring — a part of the given string.
3. Naive solution is to check for each combination of characters in the string

Are you thinking what I am thinking 🤔? Yes, this is a classic example of a problem that can be solved using the legendary technique — Sliding Window Algorithm.

Following are the steps that we will follow —

1. Have two pointers which will define the starting index start and ending index end of the current window. Both will be 0 at the beginning.
2. Declare a Set that will store all the unique characters that we have encountered.
3. Declare a variable maxLength that will keep track of the length of the longest valid substring.
4. Scan the string from left to right one character at a time.
5. If the character has not encountered before i.e., not present in the Set the we will add it and increment the end index. The maxLength will be the maximum of Set.size() and existing maxLength .
6. If the character has encounter before, i.e., present in the Set , we will increment the start and we will remove the character at start index of the string.
7. Steps #5 and #6 are moving the window.
8. After the loop terminates, return maxLength .

We are scanning the string from left to right only once, hence the time complexity will be O(n).

We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

The problem clearly states that the string contains only English letters, digits, symbols and spaces and are covered in 256 code points. Therefore, a string will be made up of a combination of these characters.

Since a Set can contain only unique elements, at any point the size of Set cannot be more than 256.

What does this mean? This means that the size of set is a function independent of the size of the input. It is a constant. Therefore, the space complexity will be O(1) (let me know in comments if you think otherwise).

After analyzing and deciding on the approach, it’s time to write some code —

package org.redquark.tutorials.leetcode; import java.util.HashSet; import java.util.Set; public class LongestSubstringWithoutRepeatingCharacters  public int lengthOfLongestSubstring(String s)  // Base condition if (s == null || s.equals(""))  return 0; > // Starting window index int start = 0; // Ending window index int end = 0; // Maximum length of substring int maxLength = 0; // This set will store the unique characters SetCharacter> uniqueCharacters = new HashSet>(); // Loop for each character in the string while (end  s.length())  if (uniqueCharacters.add(s.charAt(end)))  end++; maxLength = Math.max(maxLength, uniqueCharacters.size()); > else  uniqueCharacters.remove(s.charAt(start)); start++; > > return maxLength; > >

def lengthOfLongestSubstring(s: str) -> int: # Base condition if s == "": return 0 # Starting index of window start = 0 # Ending index of window end = 0 # Maximum length of substring without repeating characters maxLength = 0 # Set to store unique characters unique_characters = set() # Loop for each character in the string while end  len(s): if s[end] not in unique_characters: unique_characters.add(s[end]) end += 1 maxLength = max(maxLength, len(unique_characters)) else: unique_characters.remove(s[start]) start += 1 return maxLength

var lengthOfLongestSubstring = function (s)  // Base condition if (!s)  return 0; > // Starting index of the window let start = 0; // Ending index of the window let end = 0; // Maximum length of the substring let maxLength = 0; // Set to store the unique characters const uniqueCharacters = new Set(); // Loop for each character in the string while (end  s.length)  if (!uniqueCharacters.has(s[end]))  uniqueCharacters.add(s[end]); end++; maxLength = Math.max(maxLength, uniqueCharacters.size); > else  uniqueCharacters.delete(s[start]); start++; > > return maxLength; >;

fun lengthOfLongestSubstring(s: String): Int  // Base condition if (s == "")  return 0 > // Starting window index var start = 0 // Ending window index var end = 0 // Maximum length of substring var maxLength = 0 // This set will store the unique characters val uniqueCharacters: MutableSetChar> = HashSet() // Loop for each character in the string while (end  s.length)  if (uniqueCharacters.add(s[end]))  end++ maxLength = maxLength.coerceAtLeast(uniqueCharacters.size) > else  uniqueCharacters.remove(s[start]) start++ > > return maxLength >

That’s all folks! In this post, we solved LeetCode problem #3 using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!

Источник

How to find the longest non-repeating substring in a string with python

Say you want to find out the length of the longest substring in a string without any repeating characters.

As an example. Let’s say the string is as following

The output of the above would be 3 since abc is the longest substring with no repeating characters.

The Solution

To solve this problem, we’ll use a sliding window.

What is a sliding window?

This is a concept that can be used to solve a lot of problems pertaining to lists or iterables like strings. Consider there is a window superimposed over the first character of our string:

We’ll also maintain a variable which will store the value of the maximum substring with no repeating characters that we have found until now.

We are going to slide this window from the right side if the next character is different from the current character, which it is. So the window looks like this:

The same goes for the next character:

So far, we’ve been able to identify a substring that is 3 characters long and has no repeating strings. However, the next character already exists in our current substring.

What we need to do now is to slide the left end of our window such that the new character ( a in this case) is out of our window. We will match characters in our substring with the new one until we find the matching one. This will be the new left end of our window. We’ll also add the new character to our substring by sliding the right end by one character. We will also save the maximum length 3

Since the next character also exists in our substring, we’ll repeat the process from above. The maximum length stays the same. This will give us the following:

Again, the c on the right side of the window already exists in our string. Again, the maximum length stays the same as before which was 3 We’ll slide the window again.

The next character is a c . This character exists in our window and it is the last character inside it. We’ll keep matching all of our characters inside the window until we find a c which is at the end of the window. After all the necessary operations, this is what our window looks like:

The next character is added to the substring and this is our final output:

So the final output of the given string is 3

How do we implement this in python?

Code

def length_of_longest_substring(s): my_set = set() start = 0 maximum = 0 for end, value in enumerate(s): if s[end] in my_set: while s[start] != s[end]: my_set.remove(s[start]) start += 1 my_set.remove(s[start]) start += 1 my_set.add(s[end]) maximum = max(maximum, len(my_set)) return maximum

Explanation

We start off by creating a variable called my_set that will store the characters of the sliding_window. This variable is a set .

We previously talked left and right ends of this window. The variables start and end correspond to these respectively. These variables correspond to the indexes of the characters of our string. Remember, a string in python is an iterable and therefore can be looped over.

That is exactly what we do. We loop over the given string using the for loop above.

The if condition inside the for loop checks if the character is inside our window (the my_set ) or not. If it’s not, then it adds the variable to the window. It then computes the maximum length of the substring by comparing length of my_set with the previous maximum length stored in the variable maximum . It then moves on to the next character.

If the new character is found inside the loop, this means that the left end of the window needs to be slided such that the character is no longer inside the loop.

This is done by using the while loop inside the if condition:

while s[start] != s[end]: my_set.remove(s[start]) start += 1

We keep comparing the value of s[start] with the value of s[end] . It is important to note here that the value of s[end] does not change as it is the character we found inside the window. Instead we slide the left side by incrementing the value of the index start until we find the character that matches. This way the old matching character is removed from the left side of the window and the new matching character is added to the right side of it.

We keep doing this until we have parsed through the entire string. At the end of this whole operation, we are left with the maximum value of the longest substring with no repeating characters.

The sliding window can be used to solve quite a few other problems and we’ll do a dedicated post on it soon.

Источник