BiggerIsGreater in Swift & A quick tip for String performance

Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:

It must be greater than the original word

It must be the smallest word that meets the first condition

For example, given the word , the next largest word is .

Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer.

During practice on HackerRank, I met this problem. In other languages, like Python or C++, I can resolve it too easily, but not Swift. All thought, I’ve implemented the same algorithm. In some cases, the implementation did not pass all the test cases. The following is what I did to optimize the execution time.

FYI, you can find the question here https://www.hackerrank.com/challenges/bigger-is-greater/problem

The detail resolution completely finds on the internet. Here’s a short summary

• Iterating over every character, get the last value i that satisfies the given condition w[i] < w[i+1]
• Get the last value j such that w[i] < w[j]
• Swapping w[i] and w[j]. And for every character from i + 1 till the end, we sort the characters.

For example: we have a string, w=”abcedcba”

• Find out w[i] = c, i = 2
• Find out w[j] = d, j = 4
• Swap w[2] = c và w[4] = d => w = “abdeccba”
• Sorting “eccba”, we have “abcce”. So, w = “abdabcce”

I wrote the func printExecutionTime to calculate the execution time. In the article, I used a string “kpflxpezzapllerxyzlcfzyxwvutsrqponmlkjihgfedcba” and repeated for 100.

Data for testing and a function uses to calculate the execution time.

As algorithm, I implemented in a general way.

Basic solution — executionTime = 0.012266993522644043

However, It’s too slow in Swift. Noting:

• Using Array() is going to increase execution time, because of splitting string to individual character.
• We know that Swift string cannot be random access. We have to use String.Index to access. The index(, offsetBy: ) function is O(n) complexity. So, I think it’s better if you use index(before:) function instead
• The algorithmic complexity of sort() function is O(n*log n).
• In this case, It has only 26 characters. So you can use an array to count and order without using sort() function.
• The last one, Swift plays a trick called Copy-on-write. That is, if you’re just assigning the string to a new variable without any modification, they will all share the same memory space. It makes the copy of string very fast and space-efficient.

First Opt — executionTime = 0.0028690099716186523

Yeah. See the issue in back and white. But I expected a better result.

There are 2 for-loops. The first finds the minimal value from the special element to the last element then swapping it. It means that you have to through each element in the array to find only one element. That doesn’t seem right. I want to combine 2 for-loops.

Second Opt — executionTime = 0.0015190839767456055

Sound good.

Besides, using UnicodeScalar.Value has faster executionTime on the test case than asciiValue. But count for nothing.

I hope you guys enjoy and have move experience in the optimization. I believe it is certainly not a final resolution. If you have any good tips, please feel free to comment.

Have a nice day!