Blog

Longest Substring Without Repeating Characters — Leetcode #3 ( Ruby Solution )

  • Post last modified:November 10, 2023
  • Reading time:4 mins read

Ruby Solution for Leetcode #3

Introduction

We are solving a very popular and most asked leetcode question. This question is asked by companies like Facebook.

Problem Statement

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

Examples

Solution

  • Since we need to find a substring that doesn’t contain repeating characters, immediate thinking would be to list all the substrings. So in the case of “abcabcbb”, we would find and list all the possible substring combinations, [ “a”,”ab”,”abc”,”abca”, “abcab” ..]
  • Now once we have all the combinations we can remove all the strings that contain repeating characters and return the max len of the remaining string.
  • Now there are a couple of problems with this approach, first things its complex in terms of logic, second forming a combination and then searching if a repeacting character exists in the string would increase time complexity.
psuedocode
1. find all the substring of input string. TC = O(N^2) , SC = O(N)
2. find repeacting character in substring and do that for all the substring. 
    TC = O(N2), SC = O(N)
  • Can we do better? If you have learned the 2- 2-pointer approach before, it would make sense to use that. Don’t worry if you have not, we will learn from the solution so that we can identify and use it next problem.
  • In two pointers we have a left pointer and a right pointer. These 2 pointer basically drive sliding windows. and there is typically a terminating condition for which we have to adjust the window.
  • For example string “abcabcbb”, we keep the left pointer at index 0 and move the right pointer to the b. We also need to if this character is repeated or not. For that, we can keep a Set data structure which will provide faster lookup in o(1) time. Since the stack doesn’t contain b, we add a character to the stack. We do it until we find a character in the stack.
  • Once we find a character in the stack, we shift the left pointer until the occurrence of the repeating character, because now that we learn this character is repeating, a new string will always start after that character.
  • We can continue like this until the right window reaches the end.
  • One special callout in this logic is, so far we have made the first character from the left the repeating character. But we can have a case where the repeating character for the window is in the middle instead of the start of the window. For example substring “abcb”.
  • In the case of “abcb”, we need to keep shifting the left pointer until we reach to the repeating character since we know that the next substring without a repeating character will be after the repeating character we found in our window.
  • Because of this behavior, we have to use a while loop and keep removing a character from the set until we reach the point where no repeating chars in the set.
while charSet.include?(c)
        charSet.delete(s[l])
        l=l+1
end

Here is the entire working solution

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    l = 0
    charSet = Set.new
    res = 0
    s.each_char.with_index do |c, i|
      while charSet.include?(c)
        charSet.delete(s[l])
        l=l+1
      end
      charSet.add(c);
      res = [res, (i-l)+1].max
    end
    res
end

Complexity

Time complexity: O(N) Since in the sliding window none of the two pointers move in the backward direction, the window moves in a forward direction where the pointer can move O(N) steps.
Space complexity: O(N) because of Set can contain N chars when no repeating characters and an entire string is the result.

Conclusion

In this article, we used 2 pointers ( sliding window ) to solve the problem. This problem is good introduction to sliding window strategy for solving leetcode problems.

Checkout other sliding window problems at leetcode

Before You Leave

Leave a Reply