# 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.

## 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).

##### Previous Post ## Reverse Level Order Traversal

##### Next Post 