Case-specific Sorting of Strings
Given string str consisting of uppercase and lowercase characters. The task is to sort uppercase and lowercase characters separately such that if the ith place in the original string had an uppercase character, then it should not have a lowercase character after being sorted and vice versa.
Examples:
Input: str = “w3wiki”
Output: eEfggkEkrEOsS
Explanation:
uppercase characters order : EEEOS , they are in sorted order and in correct place
lowercase characters order : efggkkrs , they are in sorted order and in correct placeInput: str = “eDefSR”
Output: eDefRS
Case-specific Sorting using STL
The idea is to store lower case characters and upper case characters in two different vectors and sort both of the vectors. Then use the sorted vectors to get the sorted string. while traversing the given string
Follow the steps mentioned below to implement the approach:
- Create two vectors to store the uppercase and lowercase letters separately.
- Sort both the vector.
- Traverse The string str, and create two int i and j with value 0.
- If while traversing you found an uppercase letter then change the value with the element present at index i in the uppercase vector
and increment i by 1 - If while traversing you found a lowercase letter then change the value with the element present at index j in the lowercase vector
and increment j by 1
- If while traversing you found an uppercase letter then change the value with the element present at index i in the uppercase vector
- Print the string
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the sorted string string getSortedString(string s, int n) { // Vectors to store the lowercase // and uppercase characters vector< char > v1, v2; for ( int i = 0; i < n; i++) { if (s[i] >= 'a' && s[i] <= 'z' ) v1.push_back(s[i]); if (s[i] >= 'A' && s[i] <= 'Z' ) v2.push_back(s[i]); } // Sort both the vectors sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); int i = 0, j = 0; for ( int k = 0; k < n; k++) { // If current character is lowercase // then pick the lowercase character // from the sorted list if (s[k] >= 'a' && s[k] <= 'z' ) { s[k] = v1[i]; ++i; } // Else pick the uppercase character else if (s[k] >= 'A' && s[k] <= 'Z' ) { s[k] = v2[j]; ++j; } } // Return the sorted string return s; } // Driver code int main() { string s = "w3wiki" ; int n = s.length(); cout << getSortedString(s, n); return 0; } |
Java
// Java implementation of the approach import java.util.Collections; import java.util.Vector; class GFG { // Function to return the sorted string public static String getSortedString(StringBuilder s, int n) { // Vectors to store the lowercase // and uppercase characters Vector<Character> v1 = new Vector<>(); Vector<Character> v2 = new Vector<>(); for ( int i = 0 ; i < n; i++) { if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z' ) v1.add(s.charAt(i)); if (s.charAt(i) >= 'A' && s.charAt(i) <= 'z' ) v2.add(s.charAt(i)); } // Sort both the vectors Collections.sort(v1); Collections.sort(v2); int i = 0 , j = 0 ; for ( int k = 0 ; k < n; k++) { // If current character is lowercase // then pick the lowercase character // from the sorted list if (s.charAt(k) > = 'a' && s.charAt(k) <= 'z' ) { s.setCharAt(k, v1.elementAt(i)); ++i; } // Else pick the uppercase character else if (s.charAt(k) > = 'A' && s.charAt(k) <= 'Z' ) { s.setCharAt(k, v2.elementAt(j)); ++j; } } // Return the sorted string return s.toString(); } // Driver code public static void main(String[] args) { StringBuilder s = new StringBuilder( "w3wiki" ); int n = s.length(); System.out.println(getSortedString(s, n)); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 implementation of the approach # Function to return the sorted string def getSortedString(s, n): # Vectors to store the lowercase # and uppercase characters v1 = [] v2 = [] for i in range (n): if (s[i] > = 'a' and s[i] < = 'z' ): v1.append(s[i]) if (s[i] > = 'A' and s[i] < = 'Z' ): v2.append(s[i]) # Sort both the vectors v1 = sorted (v1) v2 = sorted (v2) i = 0 j = 0 for k in range (n): # If current character is lowercase # then pick the lowercase character # from the sorted list if (s[k] > = 'a' and s[k] < = 'z' ): s[k] = v1[i] i + = 1 # Else pick the uppercase character elif (s[k] > = 'A' and s[k] < = 'Z' ): s[k] = v2[j] j + = 1 # Return the sorted string return "".join(s) # Driver code s = "w3wiki" ss = [i for i in s] n = len (ss) print (getSortedString(ss, n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the sorted string public static String getSortedString( char [] s, int n) { // Vectors to store the lowercase // and uppercase characters List< char > v1 = new List< char >(); List< char > v2 = new List< char >(); int i = 0; for (i = 0; i < n; i++) { if (s[i] > 'a' && s[i] <= 'z' ) v1.Add(s[i]); if (s[i] > 'A' && s[i] <= 'z' ) v2.Add(s[i]); } // Sort both the vectors v1.Sort(); v2.Sort(); int j = 0; i = 0; for ( int k = 0; k < n; k++) { // If current character is lowercase // then pick the lowercase character // from the sorted list if (s[k] > 'a' && s[k] <= 'z' ) { s[k] = v1[i]; ++i; } // Else pick the uppercase character else if (s[k] > 'A' && s[k] <= 'Z' ) { s[k] = v2[j]; ++j; } } // Return the sorted string return String.Join( "" , s); } // Driver code public static void Main(String[] args) { String s = "w3wiki" ; int n = s.Length; Console.WriteLine( getSortedString(s.ToCharArray(), n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of the approach // Function to return the sorted string function getSortedString(s, n) { // Vectors to store the lowercase // and uppercase characters var v1 = []; var v2 = []; var i = 0; for (i = 0; i < n; i++) { if ( s[i].charCodeAt(0) > "a" .charCodeAt(0) && s[i].charCodeAt(0) <= "z" .charCodeAt(0) ) v1.push(s[i]); if ( s[i].charCodeAt(0) > "A" .charCodeAt(0) && s[i].charCodeAt(0) <= "Z" .charCodeAt(0) ) v2.push(s[i]); } // Sort both the vectors console.log(v1); v1.sort(); v2.sort(); var j = 0; i = 0; for ( var k = 0; k < n; k++) { // If current character is lowercase // then pick the lowercase character // from the sorted list if ( s[k].charCodeAt(0) > "a" .charCodeAt(0) && s[k].charCodeAt(0) <= "z" .charCodeAt(0) ) { s[k] = v1[i]; ++i; } // Else pick the uppercase character else if ( s[k].charCodeAt(0) > "A" .charCodeAt(0) && s[k].charCodeAt(0) <= "Z" .charCodeAt(0) ) { s[k] = v2[j]; ++j; } } // Return the sorted string return s.join( "" ); } // Driver code var s = "w3wiki" ; var n = s.length; document.write(getSortedString(s.split( "" ), n)); </script> |
eEfggkEkrEOsS
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Approach 2: Using count of Character of each case
The idea is to store lower case characters and upper-case characters count in two different int array of size 26. Now Maintain two pointers in UpperCase and Lowers Case count array. and then traverse again input string. check If currentChar is Lower case then Update it with the first available Lowercase from count array of lower case, and decrement count of that lowerCase ccharacter.and same thing to be done when Upper case character found.
C++
/*package whatever //do not write package name here */ #include <bits/stdc++.h> using namespace std; int main() { int N = 12; string str = "defRTSersUXI" ; int lowerCase[26] = { 0 }; int upperCase[26] = { 0 }; // loop to count all character upper and lower both for ( int i = 0; i < N; i++) { char ch = str[i]; if (ch >= 'a' && ch <= 'z' ) lowerCase[ch - 'a' ]++; else upperCase[ch - 'A' ]++; } string sortedStr = "" ; int loIndex = 0, upIndex = 0; // loop to traverse input str again . /* Maintain two pointer for lower case and upper case characters If currentChar is Lower case then add it first available Lowercase from count array of lower case and decrement count of that lowerCase character Same thing to be done when Upper case character found. */ for ( int i = 0; i < N; i++) { char ch = str[i]; if (ch >= 'a' && ch <= 'z' ) { if (loIndex < 26 && lowerCase[loIndex] > 0) { sortedStr += ( char )( 'a' + loIndex); lowerCase[loIndex]--; } else { while (loIndex < 26 && lowerCase[loIndex] == 0) { loIndex++; } if (loIndex < 26) { sortedStr += ( char )( 'a' + loIndex); lowerCase[loIndex]--; } } } else { if (upIndex < 26 && upperCase[upIndex] > 0) { sortedStr += ( char )( 'A' + upIndex); upperCase[upIndex]--; } else { while (upIndex < 26 && upperCase[upIndex] == 0) { upIndex++; } if (upIndex < 26) { sortedStr += ( char )( 'A' + upIndex); upperCase[upIndex]--; } } } } cout << "case sorted string is " << sortedStr; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int N = 12 ; String str = "defRTSersUXI" ; int [] lowerCase = new int [ 26 ]; int [] upperCase = new int [ 26 ]; // loop to count all character upper and lower both for ( int i = 0 ; i < N; i++) { char ch = str.charAt(i); if (ch >= 'a' && ch <= 'z' ) lowerCase[ch - 'a' ]++; else upperCase[ch - 'A' ]++; } StringBuilder sortedStr = new StringBuilder( "" ); int loIndex = 0 , upIndex = 0 ; // loop to traverse input str again . /* Maintain two pointer for lower case and upper case characters If currentChar is Lower case then add it first available Lowercase from count array of lower case and decrement count of that lowerCase character Same thing to be done when Upper case character found. */ for ( int i = 0 ; i < N; i++) { char ch = str.charAt(i); if (ch >= 'a' && ch <= 'z' ) { if (loIndex < 26 && lowerCase[loIndex] > 0 ) { sortedStr.append(( char )( 'a' + loIndex)); lowerCase[loIndex]--; } else { while (loIndex < 26 && lowerCase[loIndex] == 0 ) { loIndex++; } if (loIndex < 26 ) { sortedStr.append( ( char )( 'a' + loIndex)); lowerCase[loIndex]--; } } } else { if (upIndex < 26 && upperCase[upIndex] > 0 ) { sortedStr.append(( char )( 'A' + upIndex)); upperCase[upIndex]--; } else { while (upIndex < 26 && upperCase[upIndex] == 0 ) { upIndex++; } if (upIndex < 26 ) { sortedStr.append( ( char )( 'A' + upIndex)); upperCase[upIndex]--; } } } } System.out.println( "case sorted string is " + sortedStr.toString()); } } |
Python3
N = 12 str_ = "defRTSersUXI" lower_case = [ 0 for i in range ( 26 )] upper_case = [ 0 for i in range ( 26 )] # loop to count all character upper and lower both for i in range (N): ch = str_[i] if 'a' < = ch < = 'z' : lower_case[ ord (ch) - ord ( 'a' )] + = 1 else : upper_case[ ord (ch) - ord ( 'A' )] + = 1 sorted_str = "" lo_index = 0 up_index = 0 """loop to traverse input str again . Maintain two pointer for lower case and upper case characters If currentChar is Lower case then add it first available Lowercase from count array of lower case and decrement count of that lowerCase character Same thing to be done when Upper case character found. """ for i in range (N): ch = str_[i] if 'a' < = ch < = 'z' : if lo_index < 26 and lower_case[lo_index] > 0 : sorted_str + = chr ( ord ( 'a' ) + lo_index) lower_case[lo_index] - = 1 else : while lo_index < 26 and lower_case[lo_index] = = 0 : lo_index + = 1 if lo_index < 26 : sorted_str + = chr ( ord ( 'a' ) + lo_index) lower_case[lo_index] - = 1 else : if up_index < 26 and upper_case[up_index] > 0 : sorted_str + = chr ( ord ( 'A' ) + up_index) upper_case[up_index] - = 1 else : while up_index < 26 and upper_case[up_index] = = 0 : up_index + = 1 if up_index < 26 : sorted_str + = chr ( ord ( 'A' ) + up_index) upper_case[up_index] - = 1 print ( "case sorted string is " + sorted_str) # This code is contributed by abn95knd1. |
C#
// C# code for the above approach using System; using System.Linq; using System.Collections.Generic; class GFG { static public void Main() { int N = 12; string str = "defRTSersUXI" ; int [] lowerCase = new int [26]; int [] upperCase = new int [26]; for ( int i = 0; i < 26; i++) { lowerCase[i] = 0; upperCase[i] = 0; } // loop to count all character upper and lower both for ( int i = 0; i < N; i++) { char ch = str[i]; if (ch >= 'a' && ch <= 'z' ) lowerCase[ch - 'a' ]++; else upperCase[ch - 'A' ]++; } string sortedStr = "" ; int loIndex = 0, upIndex = 0; // loop to traverse input str again . /* Maintain two pointer for lower case and upper case characters If currentChar is Lower case then add it first available Lowercase from count array of lower case and decrement count of that lowerCase character Same thing to be done when Upper case character found. */ for ( int i = 0; i < N; i++) { char ch = str[i]; if (ch >= 'a' && ch <= 'z' ) { if (loIndex < 26 && lowerCase[loIndex] > 0) { sortedStr += ( char )( 'a' + loIndex); lowerCase[loIndex]--; } else { while (loIndex < 26 && lowerCase[loIndex] == 0) { loIndex++; } if (loIndex < 26) { sortedStr += ( char )( 'a' + loIndex); lowerCase[loIndex]--; } } } else { if (upIndex < 26 && upperCase[upIndex] > 0) { sortedStr += ( char )( 'A' + upIndex); upperCase[upIndex]--; } else { while (upIndex < 26 && upperCase[upIndex] == 0) { upIndex++; } if (upIndex < 26) { sortedStr += ( char )( 'A' + upIndex); upperCase[upIndex]--; } } } } Console.Write( "case sorted string is " + sortedStr); } } |
Javascript
let N = 12; let str= "defRTSersUXI" ; let lowerCase= new Array(26).fill(0); let upperCase= new Array(26).fill(0); //loop to count all character upper and lower both for (let i = 0; i < N;i++){ let ch = str[i]; if (ch>= 'a' && ch<= 'z' ) lowerCase[str.charCodeAt(i)-97]++; else upperCase[str.charCodeAt(i)-65]++; } let sortedStr= "" ; let loIndex=0,upIndex=0; //loop to traverse input str again . /* Maintain two pointer for lower case and upper case characters If currentChar is Lower case then add it first available Lowercase from count array of lower case and decrement count of that lowerCase character Same thing to be done when Upper case character found. */ for (let i = 0; i < N;i++){ let ch = str[i]; if (ch>= 'a' && ch<= 'z' ){ if (loIndex <26 && lowerCase[loIndex]>0){ sortedStr+=String.fromCharCode(97+loIndex); lowerCase[loIndex]--; } else { while (loIndex<26 && lowerCase[loIndex]==0){ loIndex++; } if (loIndex<26){ sortedStr+=String.fromCharCode(97+loIndex); lowerCase[loIndex]--; } } } else { if (upIndex<26 && upperCase[upIndex]>0){ sortedStr+=String.fromCharCode(65+upIndex); upperCase[upIndex]--; } else { while (upIndex<26 && upperCase[upIndex]==0){ upIndex++; } if (upIndex<26){ sortedStr+=String.fromCharCode(65+upIndex); upperCase[upIndex]--; } } } } console.log( "case sorted string is " +sortedStr); |
case sorted string is deeIRSfrsTUX
Time Complexity: O(n)
Auxiliary Space: O(n) since we are storing it in a variable for printing. If you modify existing string or keep printing each character then it will be O(26)
Approach 3: Using priority queue
- Two priority queues are created to store lowercase and uppercase characters separately. A priority queue is a container that stores elements in a particular order. In this case, we use a priority queue that stores elements in ascending order.
- A loop is used to iterate through the input string “str” and insert each character into the appropriate queue based on whether it is lowercase or uppercase.
- Another loop is used to iterate through the input string “str” again, and replace each character with the next lowest or highest character in the appropriate queue. If the character is lowercase, we replace it with the next lowest character in the lower queue. If the character is uppercase, we replace it with the next lowest character in the upper queue.
- Finally, the sorted string is returned from the function.
- Finally the sorted string is returned.
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the sorted string string getSortedString(string str, int n) { // Create two priority queues to store lowercase and // uppercase characters separately priority_queue< char , vector< char >, greater< char > > lower, upper; // Loop through the string and insert each character // into the appropriate queue for ( int i = 0; i < n; i++) { if ( islower (str[i])) { lower.push(str[i]); } else { upper.push(str[i]); } } // Loop through the string again and replace each // character with the next lowest or highest character // in the appropriate queue for ( int i = 0; i < n; i++) { if ( islower (str[i])) { str[i] = lower.top(); lower.pop(); } else { str[i] = upper.top(); upper.pop(); } } // Return the sorted string return str; } // Driver code int main() { string s = "w3wiki" ; int n = s.size(); cout << getSortedString(s, n); return 0; } // This code is contributed by Ravi Singh |
Java
import java.util.*; public class Main { // Function to return the sorted string public static String getSortedString(String str, int n) { // Create two priority queues to store lowercase and // uppercase characters separately PriorityQueue<Character> lower = new PriorityQueue<>(); PriorityQueue<Character> upper = new PriorityQueue<>(); // Loop through the string and insert each character // into the appropriate queue for ( int i = 0 ; i < n; i++) { if (Character.isLowerCase(str.charAt(i))) { lower.add(str.charAt(i)); } else { upper.add(str.charAt(i)); } } // Loop through the string again and replace each // character with the next lowest or highest // character in the appropriate queue char [] sortedStr = new char [n]; for ( int i = 0 ; i < n; i++) { if (Character.isLowerCase(str.charAt(i))) { sortedStr[i] = lower.poll(); } else { sortedStr[i] = upper.poll(); } } // Return the sorted string return new String(sortedStr); } // Driver code public static void main(String[] args) { String s = "w3wiki" ; int n = s.length(); System.out.println(getSortedString(s, n)); } } // This code is contributed by Ravi Singh |
Python3
import heapq # Function to return the sorted string def getSortedString(s: str ) - > str : # Create two priority queues to store lowercase and # uppercase characters separately lower, upper = [], [] # Loop through the string and insert each character # into the appropriate queue for i in s: if i.islower(): heapq.heappush(lower, i) else : heapq.heappush(upper, i) # Loop through the string again and replace each # character with the next lowest or highest character # in the appropriate queue res = [] for i in s: if i.islower(): res.append(heapq.heappop(lower)) else : res.append(heapq.heappop(upper)) # Return the sorted string return ''.join(res) s = "w3wiki" print (getSortedString(s)) |
Javascript
// JavaScript implementation of the approach // Function to return the sorted string function getSortedString(str) { // Create two priority queues to store lowercase and // uppercase characters separately let lower = new PriorityQueue(); let upper = new PriorityQueue(); // Loop through the string and insert each character // into the appropriate queue for (let i = 0; i < str.length; i++) { if (str[i] === str[i].toLowerCase()) { lower.enqueue(str[i]); } else { upper.enqueue(str[i]); } } let sortedStr = "" ; // Loop through the string again and replace each // character with the next lowest or highest character // in the appropriate queue for (let i = 0; i < str.length; i++) { if (str[i] === str[i].toLowerCase()) { sortedStr += lower.dequeue(); } else { sortedStr += upper.dequeue(); } } // Return the sorted string return sortedStr; } // Priority Queue class class PriorityQueue { constructor() { this .items = []; } enqueue(item) { let i = 0; while (i < this .items.length && item > this .items[i]) { i++; } this .items.splice(i, 0, item); } dequeue() { return this .items.shift(); } } // Driver code let s = "w3wiki" ; console.log(getSortedString(s)); |
C#
using System; using System.Collections.Generic; class Program { // Function to return the sorted string static string GetSortedString( string str) { // Create two priority queues to // store lowercase and // uppercase characters separately var lower = new List< char >(); var upper = new List< char >(); // Loop through the string and // insert each character // into the appropriate queue foreach ( char c in str) { if ( char .IsLower(c)) { lower.Add(c); } else { upper.Add(c); } } // Sort the queues lower.Sort(); upper.Sort(); // Loop through the string again and // replace each character with the next // lowest or highest character in the // appropriate queue var res = new char [str.Length]; int idx = 0; foreach ( char c in str) { if ( char .IsLower(c)) { res[idx] = lower[0]; lower.RemoveAt(0); } else { res[idx] = upper[0]; upper.RemoveAt(0); } idx++; } // Return the sorted string return new string (res); } // Driver Code static void Main( string [] args) { string s = "w3wiki" ; Console.WriteLine(GetSortedString(s)); } } // This code is contributed by sarojmcy2e |
eEfggkEkrEOsS
Time Complexity: O(n log n), where n is the size of the string
Auxiliary Space: O(n), space is used for implementing priority queue
Contact Us