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

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 Implementation

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

Java Code Implementation

 static void sortString(String str) {
        char []arr = str.toCharArray();
        Arrays.sort(arr);
        System.out.print(String.valueOf(arr));
 }

Python Code Implementation

def sortString(str) :
    str = ''.join(sorted(str))
    print(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.

Algorithm

• 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++ Code Implementation

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

Java Code 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 Code Implementation

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

• 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

FAQs

Q.1: How to count the frequency of characters of a string?

Ans. 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.2: What is the most efficient approach to solving this problem?

Ans: The hashing technique is the most efficient approach to solving the problem. The time complexity is O(N * 26) and the space complexity is O(1).