String.count is NOT O(1) time, but is .count on its slice O(1) time?

4 min readApr 4, 2022

ANSWER:

Swift 5 — YES, but not for every type of slice, and there are other considerations you should be aware of.

Only Swift types that conform to the RandomAccessCollection protocol get .count as an O(1) time operation.

String.count is an O(n) time operation due to complexities pertaining to the extended grapheme cluster; the entire String must first be traversed in order to know the actual size of each character. Some characters (such as emojis) are larger than others, which is why you’ll sometimes get a different length when you do string.count vs. string.utf8.count. A Swift Character is a cluster of graphemes.

— — — — — — — — — — — — — — —

We’ll need a string to use throughout this tutorial. Create that string:

let str = “my string”

— — — — — — — — — — — — — — —

APPROACH #1:

Use the following approach to convert the String into a Substring:

let sub: Substring = str[…]

Apple documentation describes a Substring as a SLICE of a String, but this is a different type of slice than the slice mentioned below in APPROACH #2.

Creating the Substring (as shown above) is an O(1) time operation, but Substring does not conform to RandomAccessProtocol; therefore, can not achieve O(1) time for substring.count.

Xcode’s Substring docs; however, state O(1) time is in fact still possible.

To achieve O(1) time the Substring would have to conform to RandomAccessCollection. In order for that to happen you would either have to:

(1) Extend Substring’s Index to conform to Strideable

(2) Implement index(_:offsetBy:) & distance(from:to:) with O(1) time

This is NOT possible however because Strideable conformance also requires its methods be implemented as O(1) time operations, which is not possible because the offsets of the String and Substring can’t be calculated in O(1) time.

The only way I can think of for a Substring to perform .count as an O(1) time operation is if it contains ≤ 1 character.

— — — — — — — — — — — — — — —

APPROACH #2:

Use the approach below to convert the String into an instance of type ArraySlice<Character>

let slice = ArraySlice(str)

#Xcode #ArraySlice #count #O(n) #O(1) #Collection #RandomAccessCollection

Invoking .count on an instance of an ArraySlice<Character> type is an O(1) operation because of ArraySlice’s conformity to RandomAccessProtocol; however, the conversion of the String into the ArraySlice takes O(n) time. So keep that in mind.

— — — — — — — — — — — — — — —

TRYING & TESTING OTHER POSSIBLE SOLUTIONS:

If you find a creative solution to find a String’s length in O(1) time, consider other costs that may be associated (ie. conversion costs).

Test the solution on different character types (ie. emojis or diacritics such as é). Ensure your potential solution returns the same length as String.count; it may not be what you expect.

If you want to compare strings via string.utf8.count, consider this:

An é created via “\u{E9}” will return a count of 2 code units.

An é created via “\u{65}\u{301}” will return a count of 3 code units.

An é created via “é” will return a count of 2 code units.

— — — — — — — — — — — — — — —

As of 04/06/22, these types conform to RandomAccessCollection: