How to Sort characters of a String in C++?

In this article, we will discuss how to sort characters ina string in C++.

Table Of Contents

Problem Description

Here we are given an a string, and we have to sort this string.

Input

string str = "abcdaabbccddeea"

If we print the string str then output must be,

aaaabbbcccddee

We can see in the output that every word is arranged alphabetically. Let’s see how we can do it using C++. There are two method to sort the string in C++. Let’s discuss them one by one.

Sort characters in a string using an array in C++

Get the occurrence count of each character in string and store that in an array of size 26. Then build the sorted string based on that array.

In this method, we will follow these steps :

1. Iterate over the whole string.
2. Store the occurrence count of every character in an array.
3. Make new string by occurrences count.
4. Print the string.

Time Complexity: O(n)
Space Complexity: O(1)

Where n is the size of the string.

Example

#include <iostream>

using namespace std;

// Driver Code
int main()
{
    string str = "abcdaabbccddeea";

    // size is fixed so space complexity is O(1)
    // in this array we will store the frequency of every element
    int a[26] = {0}; 

    // n is the size of string
    int n = str.size();

    cout << "Before string is " << str << endl;

    // Iterating
    for (int i = 0; i < n; i++)
    {
        a[str[i] - 'a']++;
    }

    // made string empty
    str = "";

    // now adding characters alphabetically
    for (int i = 0; i < 26; i++)
    {
        char add = i + 'a';
        // add storing the value which we will add in str

        // by while loop we add the character in str
        // How many time will loop run = Occurences of character
        while (a[i]--)
        {
            str += add;
        }
    }

    cout << "After string is " << str <<endl;
    return 0;
}

Output

Before string is abcdaabbccddeea
After string is aaaabbbcccdddee

Result : We can see that string has been sorted.

Sort characters in a string using STL function std::sort()

In this method we use STL function to sort the string in C++.

Time Complexity: O(nlogn)
Space Complexity: O(1)

Where n is the size of string.

Example

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string str = "abcdaabbccddeea";

    cout << "Before string is " << str << endl;

    // sort() is stl function which takes two argument 
    // first point and end point and it sorts the string.
    sort(str.begin(), str.end());

    cout << "After string is " << str << endl;
    return 0;
}

Output

Before string is abcdaabbccddeea
After string is aaaabbbcccdddee

Result : we can see string has been sorted

Summary

We have seen two different methods to sort a string. One is a naive solution which has time complexity O(n). Then another method we used the STL function.It takes O(nlogn) time. Every Method has it’s own time complexity and space complexity and own use cases. In Competitive programming if you are getting time limit exceed then you can use first method. Thanks.