Swift solution to Leetcode “Longest Substring Without Repeating Characters”

Question

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) -> Character { return (self[self.startIndex.advancedBy(index)]) } } class Solution { func lengthOfLongestSubstring(s: String) -> 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 } } 

Answer 1

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

Answer 2

The following code seems to work for me. The else of Martin didn't work for me. Ex. string "abacdef" gives me 5 as the length of the longest substring with the substring being "acdef". The longest substring in this case should be "bacdef" with length 6.

func lengthOfLongestSubstring(s: String) -> Int { var str = "" var longest = 0 for c in s { if !str.contains(c) { str.append(c) } else { longest = max(longest, str.count) let index = str.index(str.startIndex, offsetBy: 1) if str[..<index] == String(c) { str = str.replacingOccurrences(of: String(c), with: "") } else { if let index = str.index(of: c) { let nextIndex = str.index(after: index) str = String(str[nextIndex...]) } } str.append(c) } } longest = max(longest, str.count) return longest }