Given a string str containing only characters 0, 1, and 2, you can swap any two adjacent (consecutive) characters 0 and 1 or any two adjacent (consecutive) characters 1 and 2. The task is to obtain the minimum possible (lexicographically) string by using these swaps an arbitrary number of times.
Examples:
Input: str = “100210”
Output: 001120
We can swap 0 and 1 OR we can swap 1 and 2. Swapping 0 and 2 is not allowed. All the swaps can happen for adjacent only.Input: str = “2021”
Output: 1202
Note that 0 and 2 cannot be swapped
Approach: You can print all the 1s together as 1 can be swapped with either of the other characters while 0 and 2 can not be swapped, so all the 0s and 2s will follow the same order as the original string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the required stringvoid printString(string str, int n){ // count number of 1s int ones = 0; for (int i = 0; i < n; i++) if (str[i] == '1') ones++; // To check if the all the 1s // have been used or not bool used = false; for (int i = 0; i < n; i++) { if (str[i] == '2' && !used) { used = 1; // Print all the 1s if any 2 is encountered for (int j = 0; j < ones; j++) cout << "1"; } // If str[i] = 0 or str[i] = 2 if (str[i] != '1') cout << str[i]; } // If 1s are not printed yet if (!used) for (int j = 0; j < ones; j++) cout << "1";}// Driver codeint main(){ string str = "100210"; int n = str.length(); printString(str, n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to print the required stringstatic void printString(char[] str, int n){ // count number of 1s int ones = 0; for (int i = 0; i < n; i++) if (str[i] == '1') ones++; // To check if the all the 1s // have been used or not boolean used = false; for (int i = 0; i < n; i++) { if (str[i] == '2' && !used) { used = true; // Print all the 1s if any 2 is encountered for (int j = 0; j < ones; j++) System.out.print("1"); } // If str[i] = 0 or str[i] = 2 if (str[i] != '1') System.out.print(str[i]); } // If 1s are not printed yet if (!used) for (int j = 0; j < ones; j++) System.out.print("1");}// Driver codepublic static void main(String[] args) { String str = "100210"; int n = str.length(); printString(str.toCharArray(), n);}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach# Function to print the required stringdef printString(Str1, n): # count number of 1s ones = 0 for i in range(n): if (Str1[i] == '1'): ones += 1 # To check if the all the 1s # have been used or not used = False for i in range(n): if (Str1[i] == '2' and used == False): used = 1 # Print all the 1s if any 2 is encountered for j in range(ones): print("1", end = "") # If Str1[i] = 0 or Str1[i] = 2 if (Str1[i] != '1'): print(Str1[i], end = "") # If 1s are not printed yet if (used == False): for j in range(ones): print("1", end = "")# Driver codeStr1 = "100210"n = len(Str1)printString(Str1, n)# This code is contributed# by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG {// Function to print the required stringstatic void printString(char[] str, int n){ // count number of 1s int ones = 0; for (int i = 0; i < n; i++) if (str[i] == '1') ones++; // To check if the all the 1s // have been used or not bool used = false; for (int i = 0; i < n; i++) { if (str[i] == '2' && !used) { used = true; // Print all the 1s if any 2 is encountered for (int j = 0; j < ones; j++) Console.Write("1"); } // If str[i] = 0 or str[i] = 2 if (str[i] != '1') Console.Write(str[i]); } // If 1s are not printed yet if (!used) for (int j = 0; j < ones; j++) Console.Write("1");}// Driver codepublic static void Main(String[] args) { String str = "100210"; int n = str.Length; printString(str.ToCharArray(), n);}}// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the approach // Function to print the required string function printString($str, $n) { // count number of 1s $ones = 0; for ($i = 0; $i < $n; $i++) if ($str[$i] == '1') $ones++; // To check if the all the 1s // have been used or not $used = false; for ($i = 0; $i < $n; $i++) { if ($str[$i] == '2' && !$used) { $used = 1; // Print all the 1s if any 2 // is encountered for ($j = 0; $j < $ones; $j++) echo "1"; } // If str[i] = 0 or str[i] = 2 if ($str[$i] != '1') echo $str[$i]; } // If 1s are not printed yet if (!$used) for ($j = 0; $j < $ones; $j++) echo "1"; } // Driver code $str = "100210"; $n = strlen($str);printString($str, $n); // This code is contributed by Ryuga?> |
Javascript
<script> // JavaScript implementation of the approach // Function to print the required string function printString(str, n) { // count number of 1s let ones = 0; for (let i = 0; i < n; i++) if (str[i] == '1') ones++; // To check if the all the 1s // have been used or not let used = false; for (let i = 0; i < n; i++) { if (str[i] == '2' && !used) { used = true; // Print all the 1s if any 2 is encountered for (let j = 0; j < ones; j++) document.write("1"); } // If str[i] = 0 or str[i] = 2 if (str[i] != '1') document.write(str[i]); } // If 1s are not printed yet if (!used) for (let j = 0; j < ones; j++) document.write("1"); } let str = "100210"; let n = str.length; printString(str.split(''), n); </script> |
Output
001120
Time Complexity: O(n2), // since two nested loops are used the time taken by the algorithm to complete all operation is quadratic.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!