Sort String (C++, Java, and Python)

String Sort

Problem Statement

Given a string S of lowercase English characters ‘a’ – ‘z’. The task is to sort the string.

Examples:Input:  S = “dceabb”
Output: “abbcde”

Input:  S = “eeetag” 
Output: “aeeegt”

Approach 1: Using inbuilt sort

The most basic approach to solve this problem is to simply use the inbuilt sorting algorithms of the respective languages.

C++ Code

void sortString(string &str){
   sort(str.begin(), str.end());
   cout << str;

Java Code

 static void sortString(String str) {
        char []arr = str.toCharArray();

Python Code

def sortString(str) :
    str = ''.join(sorted(str))

Time Complexity: O(NlogN), where N is the length of the string.
Space Complexity: O(1) since no extra space is used.

Approach 2: Hashing

A quick observation is that the string will contain the utmost 26 unique characters. Therefore, the idea is to count the frequency of each character using a map or similar data structure. Each index of the map will represent the characters from ‘a’ – ‘z’. Therefore for each index, we can print the total number of times the given character is present.


  • Initialise a frequency array of size 26.
  • Iterate through the string and count the frequency of each character.
  • Run a loop from i = 0 till 26 and for each i, print the corresponding character freq[i] times.

C++ Implementation

const int MAX_CHAR = 26;
void sortString(string & str) {
  int charCount[MAX_CHAR] = {
  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);

Java Implementation

 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'));

Python Implementation

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="")

Time Complexity: O(N * 26), where N is the length of the string.
Space Complexity: O(1) since constant space of size 26 is used.

Practice Question – Sorted Permutation Rank


Q. How to count the frequency of characters of a string?
A. The frequency of characters can be counted using a hashmap. Iterate through the string and for each character S[i], perform freq[S[i]]++

Q. What is the most efficient approach to solving this problem?
A. The hashing technique is the most efficient approach to solve the problem. The time complexity is O(N * 26) and the space complexity is O(1).

Previous Post

Tree Diameter – Diameter of a Binary Tree

Next Post

Reverse Level Order Traversal

Exit mobile version