# String O(1) access to Character

**URL:** <https://forums.swift.org/t/string-o-1-access-to-character/19645>\
**Category:** Using Swift\
**Created:** [January 20, 2019, 2:21pm UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645 "2019-01-20T14:21:54Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![devmeremenko](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/devmeremenko/32/5890_2.png) [@devmeremenko](https://forums.swift.org/u/devmeremenko)\
**Post date:** [January 20, 2019, 2:21pm UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645/1 "2019-01-20T14:21:54Z")

</div>

Hi, I wonder whether a `Character` from a string can be received in constant time.

Currently, `String` does not support `RandomAccessCollection` which means that time complexity of the access to the random character is `O(k)` where `k` is an index from the beginning.

What if we use `ArraySlice` (which supports `RandomAccessCollection`) for this problem?

```swift
let source = "string"
let slice = ArraySlice(source)
        
(0..<slice.count).forEach { print(slice[$0]) }

```

1. Whether the time complexity is reduced to `O(n)` or `ArraySlice` anyway calls `index(_: offsetBy:)` on an underlying string that turns into `O(n^2)`?

2. Will `Array("some string")` share a common buffer with a passed string? (which means that a new memory for characters of a "some string" will not be allocated).

3. Do we have any other options to make constant time access to characters of the string?

---

<div class="post-metadata">

**Author:** ![Saklad5](https://avatars.discourse-cdn.com/v4/letter/s/4491bb/32.png) [@Saklad5](https://forums.swift.org/u/Saklad5)\
**Post date:** [January 20, 2019, 5:40pm UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645/2 "2019-01-20T17:40:44Z")

</div>

Unfortunately, I don’t think that is possible. `Character`s are extended grapheme clusters, which can be composed of multiple Unicode scalars. While you might be able to take a few shortcuts, you will never be able to receive a single `Character` in O(1) time.

I’m relatively new to Swift, so I may be wrong. That’s just my understanding based on the documentation.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [January 20, 2019, 7:43pm UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645/3 "2019-01-20T19:43:07Z")

</div>

Unlike `Slice` (which wraps an underlying `Collection` and provides a window into it), creating an `ArraySlice` creates a new buffer. So this use of `ArraySlice` is effectively the same as creating an `Array` of the string's characters (i.e. using `ArraySlice` like this is pretty much the same as writing `Array(source)[...]`). This is how it is able to give a hard guarantee of `O(1)` access, unlike `Slice` which "passes on" the complexity of the type that it wraps.

This means that the code _does_ provide constant-time access to individual characters, but it does it by allocating a new buffer, not sharing common storage. This buffer will have `Character`-size elements. A `Character` is 16 bytes, which means almost all characters will use far more storage than they need. Conversely, the emoji that don't fit inline within that 16 byte storage will allocate additional memory (unlike a string, where all the characters are stored contiguously in the string's buffer). So this ends up being a fairly inefficient way of doing this.

Another option if you do want to make this space tradeoff to gain random access would be to create an array of the _indices_ i.e. `Array(source.indices)`. This is still going to be using more memory than you need, but 8 rather than 16 bytes, and won't ever allocate additional storage. You can then access the individual elements at random via `source[idxs[4]]`.

But the next question is, why do you need random access to graphemes? There are some algorithms you might want it for, and so are willing to pay the cost of allocating memory to ensure it, but in many cases, there are other ways to achieve what you want without random access, by writing code that moves progressively through the string from start to end, using `index(_, offsetBy:)` and similar indexing API. These are fiddlier to use, but does mean that what you are trading off is programming model simplicity vs space, rather than time vs space. Hopefully there are further API that can be explored that make common tasks simpler, without compromising on efficiency.

---

<div class="post-metadata">

**Author:** ![devmeremenko](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/devmeremenko/32/5890_2.png) [@devmeremenko](https://forums.swift.org/u/devmeremenko)\
**Post date:** [January 20, 2019, 9:30pm UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645/4 "2019-01-20T21:30:08Z")

</div>

Thank you for the very detailed answer, Ben!

One of the reasons why the random access is needed is an implementation of searching algorithms. There are `KMP`, `Z-algorithm` and many others that involve getting characters by calculated `Int`-indexes.

Unfortunately, it’s not easy to implement them by moving progressively through the string from start to end. Especially, if you have to work with strings during an interview.

So, I guess `Array(string.indices)` can be a really good trade-off in the time-bound context.

> This is still going to be using more memory than you need, but 8 rather than 16 bytes, and won't ever allocate additional storage.

Does _allocate additional storage_ mean that the size of an item will remain constant 8 bytes?

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [January 21, 2019, 5:35am UTC](https://forums.swift.org/t/string-o-1-access-to-character/19645/5 "2019-01-21T05:35:36Z")

</div>

> [@devmeremenko](#):
>
> There are `KMP` , `Z-algorithm` and many others that involve getting characters by calculated `Int` -indexes.

Well... sometimes. But often you can cut back what the algorithm needs to something narrower than full random access to the entire search space. For example, many only really need to move backwards to a previously visited index never further back than the length of the pattern (i.e. if you fail matching at the nth element of the pattern you only need to go back m elements and resume matching from there). You can achieve this with a small stack or indices you push onto as you match, then discard.