2
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\begingroup\$ str.reduce(into:0){if $1=="t" {$0 += 1}} \$\endgroup\$
    – ielyamani
    Commented May 3, 2023 at 1:35
  • \$\begingroup\$ @ielyamani Great tip. Thanks a bunch! \$\endgroup\$ Commented May 3, 2023 at 4:48
  • \$\begingroup\$ There were plans to add this very feature to the standard library as a method on sequences called count(where:). Here is the related discussion on the Swift forums \$\endgroup\$
    – ielyamani
    Commented May 3, 2023 at 12:06
  • \$\begingroup\$ @ielyamani Interesting, indeed. Thanks for the link. \$\endgroup\$ Commented May 3, 2023 at 14:47

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I originally planned to return an array of String.Index. So that the caller can invoke the count self and has the indexes as well. Then discarded the idea as to complicated. Wanted something, which is simpler to use (for the caller). Missed to think the final function thoroughly through. You are perfectly right. Thanks for your helpful review. \$\endgroup\$ Commented May 3, 2023 at 4:46
  • \$\begingroup\$ The auxiliary space complexity is actually O(N²) \$\endgroup\$
    – ielyamani
    Commented May 5, 2023 at 17:29
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.