Write a program to sort characters in a string

Problem Statement: Write a program to sort characters (numbers and punctuation symbols are not included) in a given string.

Examples:

Example 1:
Input: String str = “zxcbg”
Output: bcgxz
Explanation: After sorting we get string as bcgxz

Example 2:
Input: String str = “edcba”
Output: abcde
Explanation: After sorting we get string as abcde

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Approach:

We can implement any sorting algorithm to solve this problem.

Refer to this article for an explanation along with the dry run for the Bubble sort algorithm as the below solution follows a similar approach. The bubble sort Algorithm repeatedly swaps two adjacent elements if they are in the wrong order such that the maximum element of the unsorted part is always placed in its sorted position.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
string solve(string str, int n) {

  // bubble sort
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {

      if (str[j] > str[j + 1]) {
        char temp = str[j];
        str[j] = str[j + 1];
        str[j + 1] = temp;
      }
    }
  }

  return str;
}
int main() {
  string str = "zxcbg";
  int n = str.length();

  cout << "Given string: " << "\n";
  cout << str << "\n";

  cout << "After sorting: " << "\n";
  cout << solve(str, n) << "\n";
  return 0;
}

Output:

Given string:
zxcbg
After sorting:
bcgxz

Time Complexity: O(n^2) (nested for loops)

Space Complexity: O(1) in C++

Java Code

public class tUf {

  public static String solve(String str, int n) {
    char[] arr = str.toCharArray();
    // bubble sort
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        // swap
        if (arr[j] > arr[j + 1]) {
          char temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
    String ans = new String(arr);
    return ans;
  }

  public static void main(String args[]) {
    String str = "zxcbg";
    int n = str.length();

    System.out.println("Before sorting:");
    System.out.println(str);
    System.out.println("After sorting:");
    System.out.println(solve(str, n));
  }
}

Output:

Given string:
zxcbg
After sorting:
bcgxz

Time Complexity: O(n^2) (nested for loops)

Space Complexity: O(n) in Java (because of character array)

Solution 2:

Approach:

This approach uses the sort() function in C++ and Java to sort the string.

In C++,

Sort is an in-built function in a C++ STL ( Standard Template Library)

By default, the sort() function sorts the elements in ascending order.

In Java,

As strings are immutable in Java, we first convert it to Character Array and then sort it.

To again convert this sorted array to string(to return a string), we create an object of the String class.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
string solve(string str) {
  sort(str.begin(), str.end());
  return str;
}
int main() {

  // Input string
  string str = "zxcbg";
  int length = str.length();

  cout << "String after sorting:" << "\n";
  cout << solve(str) << "\n";
  return 0;
}

Output:

String after sorting:
bcgxz

Time Complexity: O(n * log n)

Space Complexity: O(1) in C++

Java Code

import java.util.*;
public class sort_char {
  public static String solve(String str) {
    char[] char_arr = str.toCharArray();
    Arrays.sort(char_arr);
    // Creating object of String class
    String ans = new String(char_arr);
    return ans;
  }

  public static void main(String args[]) {
    String str = "zxcbg";

    System.out.println("String after sorting:");
    System.out.println(solve(str));
  }
}

Output:

String after sorting:
bcgxz

Time Complexity: O(n * log n)

Space Complexity: O(n) in Java (because of character array)

Special thanks to Rishiraj Girmal for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article