How to find the longest substring without duplicates in characters — Python solution

Photo by Sebastian Herrmann on Unsplash

Coding challenges can be head-scratching most of the time 😏. Well, for the most part, they require thorough understanding of the problem. This might involve formulating a use case and manually working through the problem with some sets of sample data.

The problem above says we should find the length of the longest sub-string without repeating characters or duplicates 🤔 .

So, if we have “pwwkew”, the non-repeating sub-strings include “pw”, “wke” and “w”, but the longest sub-string without duplicating characters is “wke”. This is because the moment we move to the next character after “e”, we hit another “w” and remember, we already have hit a previous w.

We thus need to keep track of the length of a sub-string, when it hits a duplicate and continually update the starting point of other sub-strings.

Psuedo Code

  • Define a variable that tracks the start index of the current character in our input string
  • Define a variable that holds the length of a current sub-string
  • Define a variable that holds longest length of a sub-string.
  • Traverse the string and for each already visited character, store its last occurrence in a hash table with the key as character and value as its last position.
  • While traversing the string, check whether the current character is present in hash table or not.
  • If the current index is in the hash table change the start index to the index after the current iteration.
  • If it is not present, then store current character in hash table with value as current index
  • Increment the current length by one because we updated the hash table
  • Check if the current length is greater than the longest sub-string length
  • And return the longest sub-string length.

Let’s implement this in code 🤓:

class Solution(object):
def lengthOfLongestSubstring(self, string: str) -> int:
sub = {}
cur_sub_start = 0
cur_len = 0
longest = 0
for i, letter in enumerate(string):
if letter in sub and sub[letter] >= cur_sub_start:
cur_sub_start = sub[letter] + 1
cur_len = i - sub[letter] #current - duplicate
sub[letter] = i
else:
sub[letter] = i
cur_len += 1
if cur_len > longest:
longest = cur_len

return(longest)

Conclusion

With our solution we eliminate the need to write nested loops, or to traverse the starting and ending sub-string indexes. We don’t also need to first get all possible sub-strings 😑, before implementing our criteria in code.

According to leetcode:

Longest Substring Without Repeating Characters.

Runtime: 48 ms, faster than 96.97% of Python3 online submissions for Longest Substring Without Repeating Characters. Memory Usage: 14.1 MB, less than 17.66% of Python3 online submissions for Longest Substring Without Repeating Characters.

Is this the most optimized solution? Certainly not, there are other approaches to this problem . If you have a better solution or you’ll like to improve my code, it’s here 😉 . Please feel free to leave a comment, like and share.

Thanks for the audience 🤗. connect with me on Github, linkedIn && Twitter.

Originally published at https://nextwebb.hashnode.dev.

I’m a Software Engineer 👩‍💻, an avid learner 👨‍🎓 and a community leader 🥑.