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]
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.
