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.
Confused about your next job?
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 –
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).