Rearrange a string S1 such that another given string S2 is not its subsequence
Given two strings S1 and S2 of size N and M respectively, the task is to rearrange characters in string S1 such that S2 is not a subsequence of it. If it is not possible to make such rearrangements, then print “-1”. Otherwise, print the rearranged string S1.
Examples:
Input: S1 = “abcd”, S2 = “ab”
Output: “dcba”
Explanation:
Rearrange the string S1 as “dcba”.
Now, string S2 = “ab” is not a subsequence of S1.Input: S1 = “aa”, S2 = “a”
Output: -1
Approach: Follow the steps below to solve the problem:
- Store the frequency of characters in string S2 in an auxiliary array, say cnt[26].
- Initialize a variable, say ch, to store the unique characters present in string S2.
- Traverse the array cnt[] using the variable i. If the value of cnt[i] is equal to M, this means that S2 consists of only 1 unique character. Store this character in ch and break out of the loop.
- If the value of ch is not defined, then do the following:
- Traverse the string S2 using variable i, if at any index S2[i] > S2[i + 1] sort S1 in increasing order, and break out of the loop.
- If the above condition is not encountered while traversing, sort S1 in decreasing order.
- Print the string S1.
- Otherwise, store the occurrence of ch in string S1 in freq. If the value of freq is less than M, print S1. Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to rearrange characters // in string S1 such that S2 is not // a subsequence of it void rearrangeString(string s1, string s2) { // Store the frequencies of // characters of string s2 int cnt[26] = { 0 }; // Traverse the string s2 for ( int i = 0; i < s2.size(); i++) // Update the frequency cnt[s2[i] - 'a' ]++; // Find the number of unique // characters in s2 int unique = 0; for ( int i = 0; i < 26; i++) // Increment unique by 1 if the // condition satisfies if (cnt[i] != 0) unique++; // Check if the number of unique // characters in string s2 is 1 if (unique == 1) { // Store the unique character // frequency int count_in_s2 = s2.size(); // Store occurrence of it in s1 int count_in_s1 = 0; // Find count of that character // in the string s1 for ( int i = 0; i < s1.size(); i++) // Increment count by 1 if // that unique character is // same as current character if (s1[i] == s2[0]) count_in_s1++; // If count count_in_s1 is // less than count_in_s2, then // print s1 and return if (count_in_s1 < count_in_s2) { cout << s1; return ; } // Otherwise, there is no // possible arrangement cout << -1; } else { // Checks if any character in // s2 is less than its next // character int inc = 1; // Iterate the string, s2 for ( int i = 0; i < s2.size() - 1; i++) // If s[i] is greater // than the s[i+1] if (s2[i] > s2[i + 1]) // Set inc to 0 inc = 0; // If inc=1, print s1 in // decreasing order if (inc == 1) { sort(s1.begin(), s1.end(), greater< char >()); cout << s1; } // Otherwise, print s1 in // increasing order else { sort(s1.begin(), s1.end()); cout << s1; } } } // Driver code int main() { string s1 = "abcd" , s2 = "ab" ; rearrangeString(s1, s2); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to rearrange characters // in string S1 such that S2 is not // a subsequence of it static void rearrangeString( char [] s1, char [] s2) { // Store the frequencies of // characters of string s2 int [] cnt = new int [ 26 ]; // Traverse the string s2 for ( int i = 0 ; i < s2.length; i++) // Update the frequency cnt[s2[i] - 'a' ]++; // Find the number of unique // characters in s2 int unique = 0 ; for ( int i = 0 ; i < 26 ; i++) // Increment unique by 1 if the // condition satisfies if (cnt[i] != 0 ) unique++; // Check if the number of unique // characters in string s2 is 1 if (unique == 1 ) { // Store the unique character // frequency int count_in_s2 = s2.length; // Store occurrence of it in s1 int count_in_s1 = 0 ; // Find count of that character // in the string s1 for ( int i = 0 ; i < s1.length; i++) // Increment count by 1 if // that unique character is // same as current character if (s1[i] == s2[ 0 ]) count_in_s1++; // If count count_in_s1 is // less than count_in_s2, then // print s1 and return if (count_in_s1 < count_in_s2) { System.out.print( new String(s1)); return ; } // Otherwise, there is no // possible arrangement System.out.print(- 1 ); } else { // Checks if any character in // s2 is less than its next // character int inc = 1 ; // Iterate the string, s2 for ( int i = 0 ; i < s2.length - 1 ; i++) // If s[i] is greater // than the s[i+1] if (s2[i] > s2[i + 1 ]) // Set inc to 0 inc = 0 ; // If inc=1, print s1 in // decreasing order if (inc == 1 ) { Arrays.sort(s1); for ( int k = 0 ; k < s1.length / 2 ; k++) { char temp = s1[k]; s1[k] = s1[s1.length - k - 1 ]; s1[s1.length - k - 1 ] = temp; } System.out.print( new String(s1)); } // Otherwise, print s1 in // increasing order else { Arrays.sort(s1); System.out.print( new String(s1)); } } } // Driver code public static void main(String[] args) { char [] s1 = "abcd" .toCharArray(); char [] s2 = "ab" .toCharArray(); rearrangeString(s1, s2); } } // This code is contributed by divyesh072019 |
Python3
# Python3 program for the above approach # Function to rearrange characters # in S1 such that S2 is not # a subsequence of it def rearrangeString(s1, s2): # Store the frequencies of # characters of s2 cnt = [ 0 ] * 26 # Traverse the s2 for i in range ( len (s2)): # Update the frequency cnt[ ord (s2[i]) - ord ( 'a' )] + = 1 # Find the number of unique # characters in s2 unique = 0 for i in range ( 26 ): # Increment unique by 1 if the # condition satisfies if (cnt[i] ! = 0 ): unique + = 1 # Check if the number of unique # characters in s2 is 1 if (unique = = 1 ): # Store the unique character # frequency count_in_s2 = len (s2) # Store occurrence of it in s1 count_in_s1 = 0 # Find count of that character # in the s1 for i in range ( len (s1)): # Increment count by 1 if # that unique character is # same as current character if (s1[i] = = s2[ 0 ]): count_in_s1 + = 1 # If count count_in_s1 is # less than count_in_s2, then # prs1 and return if (count_in_s1 < count_in_s2): print (s1, end = "") return # Otherwise, there is no # possible arrangement print ( - 1 , end = "") else : # Checks if any character in # s2 is less than its next # character inc = 1 # Iterate the string, s2 for i in range ( len (s2) - 1 ): # If s[i] is greater # than the s[i+1] if (s2[i] > s2[i + 1 ]): # Set inc to 0 inc = 0 # If inc=1, prs1 in # decreasing order if (inc = = 1 ): s1 = sorted (s1)[:: - 1 ] print (" ".join(s1), end = " ") # Otherwise, prs1 in # increasing order else : s1 = sorted (s1) print (" ".join(s1), end = " ") # Driver code if __name__ = = '__main__' : s1, s2 = "abcd" , "ab" rearrangeString(s1, s2) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { // Function to rearrange characters // in string S1 such that S2 is not // a subsequence of it static void rearrangeString( char [] s1, char [] s2) { // Store the frequencies of // characters of string s2 int [] cnt = new int [26]; // Traverse the string s2 for ( int i = 0; i < s2.Length; i++) // Update the frequency cnt[s2[i] - 'a' ]++; // Find the number of unique // characters in s2 int unique = 0; for ( int i = 0; i < 26; i++) // Increment unique by 1 if the // condition satisfies if (cnt[i] != 0) unique++; // Check if the number of unique // characters in string s2 is 1 if (unique == 1) { // Store the unique character // frequency int count_in_s2 = s2.Length; // Store occurrence of it in s1 int count_in_s1 = 0; // Find count of that character // in the string s1 for ( int i = 0; i < s1.Length; i++) // Increment count by 1 if // that unique character is // same as current character if (s1[i] == s2[0]) count_in_s1++; // If count count_in_s1 is // less than count_in_s2, then // print s1 and return if (count_in_s1 < count_in_s2) { Console.Write( new string (s1)); return ; } // Otherwise, there is no // possible arrangement Console.Write(-1); } else { // Checks if any character in // s2 is less than its next // character int inc = 1; // Iterate the string, s2 for ( int i = 0; i < s2.Length - 1; i++) // If s[i] is greater // than the s[i+1] if (s2[i] > s2[i + 1]) // Set inc to 0 inc = 0; // If inc=1, print s1 in // decreasing order if (inc == 1) { Array.Sort(s1); Array.Reverse(s1); Console.Write( new string (s1)); } // Otherwise, print s1 in // increasing order else { Array.Sort(s1); Console.Write( new string (s1)); } } } // Driver code static void Main() { char [] s1 = "abcd" .ToCharArray(); char [] s2 = "ab" .ToCharArray(); rearrangeString(s1, s2); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Function to rearrange characters // in string S1 such that S2 is not // a subsequence of it function rearrangeString(s1, s2) { // Store the frequencies of // characters of string s2 let cnt = new Array(26); cnt.fill(0); // Traverse the string s2 for (let i = 0; i < s2.length; i++) // Update the frequency cnt[s2[i].charCodeAt() - 'a' .charCodeAt()]++; // Find the number of unique // characters in s2 let unique = 0; for (let i = 0; i < 26; i++) // Increment unique by 1 if the // condition satisfies if (cnt[i] != 0) unique++; // Check if the number of unique // characters in string s2 is 1 if (unique == 1) { // Store the unique character // frequency let count_in_s2 = s2.length; // Store occurrence of it in s1 let count_in_s1 = 0; // Find count of that character // in the string s1 for (let i = 0; i < s1.length; i++) // Increment count by 1 if // that unique character is // same as current character if (s1[i] == s2[0]) count_in_s1++; // If count count_in_s1 is // less than count_in_s2, then // print s1 and return if (count_in_s1 < count_in_s2) { document.write(s1.join( "" )); return ; } // Otherwise, there is no // possible arrangement document.write(-1); } else { // Checks if any character in // s2 is less than its next // character let inc = 1; // Iterate the string, s2 for (let i = 0; i < s2.length - 1; i++) // If s[i] is greater // than the s[i+1] if (s2[i].charCodeAt() > s2[i + 1].charCodeAt()) // Set inc to 0 inc = 0; // If inc=1, print s1 in // decreasing order if (inc == 1) { s1.sort(); s1.reverse(); document.write(s1.join( "" )); } // Otherwise, print s1 in // increasing order else { s1.sort(); document.write(s1.join( "" )); } } } let s1 = "abcd" .split( '' ); let s2 = "ab" .split( '' ); rearrangeString(s1, s2); </script> |
Output:
dcba
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Contact Us