Swift solution to Leetcode “Longest Substring Without Repeating Characters” From LeetCode medium 3. Longest Substring Without Repeating Characters:


  Given a string, find the length of the longest substring without repeating characters.
  
  Examples:
  
  Given "abcabcbb", the answer is "abc", which the length is 3.
  
  Given "bbbbb", the answer is "b", with the length of 1.
  
  Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.


Here is my solution, but the online judge told me "Time Limit Exceeded". Is there a better solution to this problem?

private extension String
{
    subscript (index:Int) -&gt; Character
    {
        return (self[self.startIndex.advancedBy(index)])
    }
}

class Solution
{
    func lengthOfLongestSubstring(s: String) -&gt; Int
    {
        var str:String = ""
        var longest:Int = Int.min

        if s.isEmpty
        {
            return 0
        }

        for i in 0...s.characters.count-1
        {
            if !str.characters.contains(s[i])
            {
                str += String(s[i])
            }

            else
            {
                longest = max(longest, str.characters.count)
                str = ""

            }
        }

        return longest
    }
}
The Swift standard library does not have a built-in method to access the
n'th character of a string. It is tempting to fill that gap with a custom
extension like you did, but the problem is that

self[self.startIndex.advancedBy(index)]


is a \$ O(index) \$  operation. In contrast to other languages where a
"character" is a fixed-size object (and accessing the n'th character of
a string a  \$ O(1) \$  operation), a Swift Character represents a 
"Unicode grapheme cluster" which consists of one or more Unicode scalar
values, see e.g. Strings in Swift 2 in the Swift blog.

That makes

for i in 0...s.characters.count-1 {
    // access `s[i]` with your custom subscript method
}


a O(n^2) operation where n is the number of characters in the string.
It is much more efficient to iterate over the characters with

for c in s.characters {
    // do something with `c`
}


More remarks:


The explicit type annotations in

var str:String = ""
var longest:Int = Int.min


are not necessary, the compiler can infer the type automatically.
If you start with var longest = 0 then the special case

if s.isEmpty
{
    return 0
}


becomes obsolete.
There are actually two errors in your code. If a repeating
character is found then the new substring candidate consists of
that character, i.e.

 longest = max(longest, str.characters.count)
 str = ""


should be

 longest = max(longest, str.characters.count)
 str = String(s[i])


otherwise lengthOfLongestSubstring("aabcdd") returns 3 instead
of 4.

And the longest substring length must also be updated at the end
of the string:

longest = max(longest, str.characters.count)
return longest


otherwise lengthOfLongestSubstring("aabcd") returns 1 instead
of 4.


Putting all that together, the method becomes

func lengthOfLongestSubstring(s: String) -&gt; Int {
    var str = ""
    var longest = 0

    for c in s.characters {
        if !str.characters.contains(c) {
            str.append(c)
        } else {
            longest = max(longest, str.characters.count)
            str = String(c)
        }
    }
    longest = max(longest, str.characters.count)
    return longest
}


which should be faster than your code.

Another possible improvement is to store the characters of the
current substring in an Array or a Set instead of a String.
Which one is faster depends on the size of the strings, here is
an example with an array:

func lengthOfLongestSubstring(s: String) -&gt; Int {
    var substringChars: [Character] = []
    var longest = 0

    for c in s.characters {
        if !substringChars.contains(c) {
            substringChars.append(c)
        } else {
            longest = max(longest, substringChars.count)
            substringChars = [c]
        }
    }
    longest = max(longest, substringChars.count)
    return longest
}


As of Swift 4, a Swift string is a collection of its characters
again, so  for c in s.characters can be simplified to for c in s.