TIL - We can optimize String Sort further 🤘

Get to know about a effective optimization technique

Context

• Sometimes when you are solving questions on Leetcode, you notice a question where you can’t optimize your current solution approach further.

• What do you do in this case?

  • Well, you can try to build your own custom method(function) in specific scenarios where your own methods can become more efficient than the inbuilt methods.

• I was stuck in a similar situation:

  • I was trying to solve a question in which input was in the form of array of strings.

  • As part of my solution approach, I had to sort the strings one by one while iterating over them.

  • But, the solution approach was not that efficient.

Problem Statement

Optimize sorting of a string

• In C++, we usually make use of STL library.

• It provides a sort() method which implements the sort in O(N * log(N)) considering the worst-case scenario. (Here, ‘N’ represents the size of the string)

• So how can we optimize this?

Few Hints

• Check if all the characters in the string follow a same pattern?

• Are all distinct characters just the alphabetical ones?

• If yes, then we know that there are only 26 alphabets. How can we make use of this information?

• Are all the characters in lowercase, or all are in uppercase?

Solution Approach

IMPORTANT: For this approach, we are going to assume these points:

• string will have characters only from ‘a’ to ‘z’

• all characters are in lowercase

1. Create an integer array of fixed length of 26

2. Make all the array elements equal to 0

3. Iterate over the characters of string, and store the count of the characters

   1. Subtract ‘a’ from each character

      1. for ex-

         1. ‘a‘-’a’ gives value as 0

         2. ‘b’-’a’ gives 1

         3. ‘c’ - ‘a’ gives 2

         4. . . . and so on

   2. This way, all the characters in the string can be mapped to the integer array of size 26

   3. Increment the specific element value of the array, each time when a character gets mapped to that specific index

4. This time, iterate over the integer array to rebuild the complete string

5. We now have the sorted string!

RESULT -

• The time complexity of our solution is O(N)🔥 - a nice improvement from O(N*log(N)).

• TAKEAWAY -

  • Keep close eye on the similar string patterns

  • This same solution approach can be used in situations where all characters are either in uppercase, or they are numbers from 0 - 9, etc

    • Ex - “BACCBA“, “926712”

Code Snippet of logic in C++

That’s it. UNTIL NEXT TIME!