Swift-function, which counts all occurrences of a character within a string

Question

I wrote this function, which (shall) count all occurrences of a specified character within a given string.

func countOccurrence(of char: Character, within str: String) -> Int {
    var strCopy = str
    var indexes = [String.Index]()

    while true {
        let curr = strCopy.firstIndex(of: char)
        if let curr = curr {
            indexes.append(curr)
            let indexAfter = str.index(after: curr)
            strCopy = String(strCopy[indexAfter..<strCopy.endIndex])
        } else {
            break
        }
    }

    return indexes.count
}

let sTest = "Testing Swift, today Tuesday 123 ! tt".lowercased()
print(countOccurrence(of: "t", within: sTest)) // Result: 7

let sTest2 = "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor.".lowercased()
print(countOccurrence(of: "s", within: sTest2)) // Result: 4

Can I expect my function to work as expected or does someone see any flaws?

Can it become improved? Respectively, does someone know a better solution for the described task?

Answer 1

This function appears to be very expensive. I don't know the right way to author it, but it isn't the current code.

Consider this task: look for occurrences of "a", in an input string of a thousand "a"'s. That is, input length N = 1000.

            indexes.append(curr)
            ...
            strCopy = String(strCopy[indexAfter..<strCopy.endIndex])

Why the .append()? Why allocate? We need to return an integer, yet the space complexity is O(N) ?

Why the copy? We duplicate everything from current index to end-of-string, rather than using an efficient string view. By the end of it we've copied half a million characters. Time complexity is O(N^2).

To propose a quadratic algorithm for a linear task suggests that you'll want to return to the drawing board and examine the problem's requirements more closely. Don't allocate for each index. Don't copy characters.

Just scan and increment.

Answer 2

I found something short that works out of the box:

"Testing Swift, today Tuesday 123 ! tt".lowercased().ranges(of: "t").count // Result: 7

I have no idea how well it performs.

---

I would propose to write your function as an extension of String. This makes coding easier, because then it will auto-complete on any String:

extension String {
    func countOccurrences(of char: Character) -> Int {
        self.ranges(of: String(char)).count
    }
}

---

We can also add more flexibility:

extension String {
    func countOccurrences(of string: String, caseSensitive: Bool = true) -> Int {
        if caseSensitive {
            return self.ranges(of: string).count
        } else {
            return self.lowercased().ranges(of: string.lowercased()).count
        }
    }
}

so when can use it like this:

let sTest = "Testing Swift, today Tuesday 123 ! tt"
sTest.countOccurrences(of: "T") // result 2
sTest.countOccurrences(of: "T", caseSensitive: false) // result 7
sTest.countOccurrences(of: "tt") // result 1