Sort string of characters

Last Updated : 15 Oct, 2024

Given a string of lowercase characters from ‘a’ – ‘z’. We need to write a program to print the characters of this string in sorted order.

Examples:

Input : “dcab”
Output : “abcd”

Input : “geeksforgeeks”
Output : “eeeefggkkorss”

Naive Approach – O(n Log n) Time

A simple approach is to use sorting algorithms like quick sort or merge sort and sort the input string and print it.

C++

// C++ program to sort a string of characters
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s = "geeksforgeeks";    
    sort(s.begin(), s.end());
    cout << s;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// comparison function for qsort
int compare(const void *a, const void *b)
{
    return (*(char *)a - *(char *)b);
}

// function to print string in sorted order
void sortString(char *str)
{
    int n = strlen(str);
    qsort(str, n, sizeof(char), compare);
    printf("%s", str);
}

// Driver program to test above function
int main()
{
    char s[] = "geeksforgeeks";
    sortString(s);
    return 0;
}

Java

import java.util.Arrays;

public class GfG {
  
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        
        // Convert the string to a character array
        char[] arr = s.toCharArray();

        // Sort the character array
        Arrays.sort(arr);

        // Convert sorted character array back to string
        s = new String(arr);

        // Print the sorted string
        System.out.print(s);
    }
}

Python

s = "geeksforgeeks"

# Sort the string and join it back
s = ''.join(sorted(s))

# Print the sorted string
print(s)

using System;

class GfG {
    static void Main() {
        string s = "geeksforgeeks";

        // Convert the string to a character array
        char[] arr = s.ToCharArray();

        // Sort the character array
        Array.Sort(arr);

        // Convert sorted character array back to string
        s = new string(arr);

        // Print the sorted string
        Console.Write(s);
    }
}

JavaScript

let s = "geeksforgeeks";

// Sort the string by converting 
// it to an array, sorting, and joining back
s = s.split('').sort().join('');

// Print the sorted string
console.log(s);

Output

eeeefggkkorss

Efficient Approach – O(n) Time

An efficient approach will be to observe first that there can be a total of 26 unique characters only. So, we can store the count of occurrences of all the characters from ‘a’ to ‘z’ in a hashed array. The first index of the hashed array will represent character ‘a’, second will represent ‘b’ and so on. Finally, we will simply traverse the hashed array and print the characters from ‘a’ to ‘z’ the number of times they occurred in input string.

Below is the implementation of above idea:

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_CHAR = 26;

// Function to print string in sorted order
void sortString(string &s) {
  
    // Count array to keep count of characters
    int charCount[MAX_CHAR] = {0};
    
    // Traverse string and increment count of characters
    for (int i = 0; i < s.length(); i++) {
      
        // 'a'-'a' will be 0, 'b'-'a' will be 1, etc.
        charCount[s[i] - 'a']++;
    }
    
    // Traverse the hash array and print characters
    for (int i = 0; i < MAX_CHAR; i++) {
        for (int j = 0; j < charCount[i]; j++) {
            cout << (char)('a' + i);
        }
    }
}

int main() {
    string s = "geeksforgeeks";    
    sortString(s);    
    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAX_CHAR 26

// Function to print string in sorted order
void sortString(char s[]) {
    int charCount[MAX_CHAR] = {0};
    
    // Traverse the string and count characters
    for (int i = 0; i < strlen(s); i++) {
        charCount[s[i] - 'a']++;
    }
    
    // Traverse the count array and print characters
    for (int i = 0; i < MAX_CHAR; i++) {
        for (int j = 0; j < charCount[i]; j++) {
            printf("%c", 'a' + i);
        }
    }
}

int main() {
    char s[] = "geeksforgeeks";    
    sortString(s);    
    return 0;
}

Java

public class GfG {
    static final int MAX_CHAR = 26;

    // Function to print string in sorted order
    static void sortString(String s) {
        int[] charCount = new int[MAX_CHAR];
        
        // Traverse the string and count characters
        for (int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
        }
        
        // Traverse the count array and print characters
        for (int i = 0; i < MAX_CHAR; i++) {
            for (int j = 0; j < charCount[i]; j++) {
                System.out.print((char)('a' + i));
            }
        }
    }

    public static void main(String[] args) {
        String s = "geeksforgeeks";
        sortString(s);
    }
}

Python

MAX_CHAR = 26

# Function to print string in sorted order
def sortString(s):
    charCount = [0] * MAX_CHAR
    
    # Traverse the string and count characters
    for ch in s:
        charCount[ord(ch) - ord('a')] += 1
    
    # Traverse the count array and print characters
    for i in range(MAX_CHAR):
        for _ in range(charCount[i]):
            print(chr(i + ord('a')), end='')

s = "geeksforgeeks"
sortString(s)

using System;

class GfG {
    const int MAX_CHAR = 26;

    // Function to print string in sorted order
    static void sortString(string s) {
        int[] charCount = new int[MAX_CHAR];
        
        // Traverse the string and count characters
        foreach (char ch in s) {
            charCount[ch - 'a']++;
        }
        
        // Traverse the count array and print characters
        for (int i = 0; i < MAX_CHAR; i++) {
            for (int j = 0; j < charCount[i]; j++) {
                Console.Write((char)('a' + i));
            }
        }
    }

    static void Main() {
        string s = "geeksforgeeks";
        sortString(s);
    }
}

JavaScript

const MAX_CHAR = 26;

// Function to print string in sorted order
function sortString(s) {
    const charCount = new Array(MAX_CHAR).fill(0);
    
    // Traverse the string and count characters
    for (let ch of s) {
        charCount[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // Traverse the count array and print characters
    for (let i = 0; i < MAX_CHAR; i++) {
        for (let j = 0; j < charCount[i]; j++) {
            process.stdout.write(String.fromCharCode('a'.charCodeAt(0) + i));
        }
    }
}

const s = "geeksforgeeks";
sortString(s);

Output

eeeefggkkorss

Time Complexity:O(Max_CHAR*n) which becomes O(n) as MAX_CHAR is constant,So Overall Time Complexity:- O(n) where n is the length of the string.
Auxiliary Space:O(Max_CHAR).