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 : bbccdefbbaa
Output : aabbbbccdef
Input : geeksforgeeks
Output : eeeefggkkorss
A simple approach will be to use sorting algorithms like quick sort or merge sort and sort the input string and print it.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
void sortString(string &str)
{
sort(str.begin(), str.end());
cout << str;
}
int main()
{
string s = "geeksforgeeks";
sortString(s);
return 0;
}
|
Java
import java.util.Arrays;
class GFG {
static void sortString(String str) {
char []arr = str.toCharArray();
Arrays.sort(arr);
System.out.print(String.valueOf(arr));
}
public static void main(String[] args) {
String s = "geeksforgeeks";
sortString(s);
}
}
|
Python3
def sortString(str) :
str = ''.join(sorted(str))
print(str)
s = "geeksforgeeks"
sortString(s)
|
C#
using System;
public class GFG {
static void sortString(String str) {
char []arr = str.ToCharArray();
Array.Sort(arr);
Console.WriteLine(String.Join("",arr));
}
public static void Main() {
String s = "geeksforgeeks";
sortString(s);
}
}
|
Javascript
<script>
let MAX_CHAR = 26;
function sortString(str)
{
let charCount = new Array(MAX_CHAR);
charCount.fill(0);
for (let i = 0; i < str.length; i++)
charCount[str[i].charCodeAt()-'a'.charCodeAt()]++;
for (let i=0;i<MAX_CHAR;i++)
for (let j=0;j<charCount[i];j++)
document.write(String.fromCharCode('a'.charCodeAt()+i) );
}
let s = "geeksforgeeks";
sortString(s);
</script>
|
Time Complexity: O(n log n), where n is the length of string.
Auxiliary Space: O( 1 ).
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:
Implementation:
C
#include <stdio.h>
#include <string.h>
void swap(char* a, char* b)
{
char temp = *a;
*a = *b;
*b = temp;
}
int partition(char* str, int low, int high)
{
char pivot = str[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (str[j] <= pivot) {
i++;
swap(&str[i], &str[j]);
}
}
swap(&str[i + 1],
&str[high]);
return i + 1;
}
void quickSort(char* str, int low, int high)
{
if (low < high) {
int pivotIndex = partition(
str, low, high);
quickSort(str, low,
pivotIndex
- 1);
quickSort(str, pivotIndex + 1,
high);
}
}
int main()
{
char str[] = "geeksforgeeks";
int n = strlen(str);
quickSort(str, 0, n - 1);
printf("Sorted string: %s\n", str);
return 0;
}
|
C++
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
void sortString(string &str)
{
int charCount[MAX_CHAR] = {0};
for (int i=0; i<str.length(); i++)
charCount[str[i]-'a']++;
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;
}
|
Java
public class SortString{
static final int MAX_CHAR = 26;
static void sortString(String str) {
int letters[] = new int[MAX_CHAR];
for (char x : str.toCharArray()) {
letters[x - 'a']++;
}
for (int i = 0; i < MAX_CHAR; i++) {
for (int j = 0; j < letters[i]; j++) {
System.out.print((char) (i + 'a'));
}
}
}
public static void main(String[] args) {
sortString("geeksforgeeks");
}
}
|
Python3
MAX_CHAR = 26
def sortString(str):
charCount = [0 for i in range(MAX_CHAR)]
for i in range(0, len(str), 1):
charCount[ord(str[i]) - ord('a')] += 1
for i in range(0, MAX_CHAR, 1):
for j in range(0, charCount[i], 1):
print(chr(ord('a') + i), end = "")
if __name__ == '__main__':
s = "geeksforgeeks"
sortString(s)
|
C#
using System;
class GFG
{
public static string sortString(string inputString)
{
char[] tempArray = inputString.ToCharArray();
Array.Sort(tempArray);
return new string(tempArray);
}
public static void Main(string[] args)
{
string inputString = "geeksforgeeks";
Console.WriteLine(sortString(inputString));
}
}
|
Javascript
<script>
let MAX_CHAR = 26;
function sortString(str)
{
let letters=new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
{
letters[i]=0;
}
for(let x=0;x<str.length;x++)
{
letters[str[x].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let i = 0; i < MAX_CHAR; i++) {
for (let j = 0; j < letters[i]; j++) {
document.write(String.fromCharCode
(i + 'a'.charCodeAt(0)));
}
}
}
sortString("geeksforgeeks");
</script>
|
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( 1 ).
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!