Longest Substring without Repeating

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.

Looking for a brute force solution of this problem would be looking through all the possible substrings of the input and finding any that don't have duplicate characters allowing us to return the count of the longest one. I think we can do better. Here is the problem skeleton from leetcode:

func lengthOfLongestSubstring(_ s: String) -> Int {
}

The first thing we can do is add a simple check to make sure the string is not empty. If the string is empty then we know that it contains no substrings. Then answer should be 0.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
}

In order to solve this problem we are going to need to iterate over the strings and building up substrings. We need to keep track of where are substring starts and what letter in the string our current substring is. Since we will be looking at multiple substrings in the word we will also need to keep track of our current longest substring starting index and ending index. Let's set up some variables to keep track of that.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
}

We have set up startIndex here to keep track of the beginning of our current substring and started it at 0 or the beginning of the input string. We also have set up longest to hold the starting and ending index of the longest substring that we have found so far. Since we know that the string has at least one character (because we checked if it was empty) we know that at least the first letter will be a substring that doesn't repeat characters. We start with that as the longest and store the indices in our array. Finally we need to keep track of letters that we have seen to make sure we start our substring again once we see a repeat letter.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
}

We are ready to start looking for substrings now. Lets create our loop over the input string keeping track of the current letter and the index in the string

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
  for (index, char) in s.enumerated() {
    
  }
}

We first need to check and see if we have seen the letter before. We make a quick check in our hash to find out if it is there. If it is there we will need to move our startIndex to begin a tracking a new substring. We will want to see if the starting index of our substring needs to be updated. In order to do this we will compare the current starting index of our substring to the index when we last saw the current character. If that index (the one for the last time we saw our character) is before our starting index of this substring it's not currently part of the substring so we don't need to update anything. If the index is greater than or equal to (meaning we saw that letter before in this current substring we want to move our starting index to the index immediately after it.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
  for (index, char) in s.enumerated() {
    if let prevIndex = hash[char] {
      if startIndex <= prevIndex {
        startIndex = prevIndex + 1
    }
  }
}

We also need to check if the current substring is now longer than our previous longest substring. If it is we need to update the indices in our array.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
  for (index, char) in s.enumerated() {
    if let prevIndex = hash[char] {
      if startIndex <= prevIndex {
        startIndex = prevIndex + 1
    }
    if longest[1] - longest[0] < index - startIndex + 1 {
      longest = [startIndex, index + 1]
    }
  }
}

Finally we need to update the hash table of previously seen characters.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
  for (index, char) in s.enumerated() {
    if let prevIndex = hash[char] {
      if startIndex <= prevIndex {
        startIndex = prevIndex + 1
    }
    if longest[1] - longest[0] < index - startIndex + 1 {
      longest = [startIndex, index + 1]
    }
    hash[char] = index
  }
}

Once we have that we can just return the difference between the 2 indices that we have in our longest array.

func lengthOfLongestSubstring(_ s: String) -> Int {
  if s.isEmpty { return 0 }
  var startIndex: Int = 0
  var longest = [0, 1]
  var hash = [Character: Int]()
  for (index, char) in s.enumerated() {
    if let prevIndex = hash[char] {
      if startIndex <= prevIndex {
        startIndex = prevIndex + 1
    }
    if longest[1] - longest[0] < index - startIndex + 1 {
      longest = [startIndex, index + 1]
    }
    hash[char] = index
  }
  return longest[1] - longest[0]
}