How to iterate on a string using subscripts in swift

Question

I come from a java background and String slicing in swift appears very verbose and difficult to me. I am trying to answer this leet code question with an algorithm that works with subscripts.

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.

Here is my code:

func lengthOfLongestSubstring(_ s: String) -> Int {
 var maximum = 0
 var start = 0
 var end = 0
 var set = Set<Character>()
 while end < s.count{
     if set.contains(s[end]){
         set.remove(s[start])
         start+=1
     }
     else{
         set.insert(s[end])
         end+=1
         maximum = max(maximum, end-start)
     }
 }
}

I worked with Int subscripts. But I get this error message: 'subscript(_:)' is unavailable: cannot subscript String with an Int, use a String.Index instead. How can I solve it without getting too verbose?

Answer 1

Other languages make simplifying assumptions about Unicode strings that Swift does not. You can't be sure how many code-points a given character takes to store, so each time you index to the nth character of a unicode string it is an O(n) operation. Thus code that uses random access integer indexing into Unicode has unexpected O(n²) performance. For that reason Swift does not offer integer indexing.

The simple way to get integer indexing into the characters of a Swift string, as Matt suggests in his comment, is to convert the String to an Array of characters. You'll pay the O(n) cost for that conversion ONCE (as well as memory costs for extra storage) and then have fixed-time access to characters after that.

Alternately you can learn how to index into Swift strings using a String.Index, but that will require you to change your current approach.

Answer 2

Why is it so difficult to accessing characters in a string?

If strings would be made of fixed sized characters stored in arrays, finding the n-th character would be straightforward and efficient using an integer subscript.

But popular string encodings such as UTF-8 and UTF-16 use a variable number of bytes/words to store characters. So a direct access to the n-th character requires counting characters one by one from the start or other costly strategies, to deal correctly with strings such as "Abçdefg" (9 characters, but 11 UTF16 words and 16 UTF8 bytes)

Quick fix

Since the subscript requires an index and you work with integers, you can get rid of the error, by replace the faulty s[i] with:

s[s.index(s.startIndex, offsetBy: i))]

This is not very concise. But it has the advantage of drawing your attention at the complexity of computing and indexes from an integer character count. (And if you'd profile your code working with very long strings, you'll quickly find out it's a bottleneck).

How about making better use of indexes?

On the other side, many algorithms (including yours) access characters one after another. So there is no need to recount characters from the start over and over again, if you work with relative positions. For this reason, Swift designers chose to subscript strings with indexes.

A better approach would therefore be to use Swift's native way: work with indexes instead of integers and iterate over the string:

func lengthOfLongestSubstring(_ s: String) -> Int {
    var maximum = 0
    var start = s.startIndex   // starting at start of the string
    var end = s.startIndex
    var set = Set<Character>()
    while end != s.endIndex{  // is end of string reached ? 
        if set.contains(s[end]){
            set.remove(s[start])
            start = s.index(after: start)  // going to the next character
        }
        else{
            set.insert(s[end])
            end = s.index(after:end)    // going to the next character
            maximum = max(maximum, s.distance(from: start, to:end)) // count characters between indexes
        }
    }
    return maximum
}

Here a quick introduction on useful indexing functions.