Given two numeric strings N and K (K ? N), where digits of K are in non-decreasing order, the task is to rearrange digits of N such that K does not appear as a subsequence in N. If it is not possible to obtain such a permutation, print “-1”. Otherwise print any such valid permutation of N.
Examples:
Input: N = 93039373637, K = 339
Output: 97093736333Input: N=965, K=55
Output: 965
Naive Approach: The simplest approach is to generate every permutation of N and check for each permutation, if K appears as a subsequence in it or not. If found to be false for any permutation, print that permutation.
Time Complexity: O(N*N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the observation that the digits of K are in non-decreasing order. Therefore, rearrange the digits of N in decreasing order by sorting. Follow the steps below to solve the problem:
- Store the frequency of digits of N and K in HashMaps M1 and M2, respectively.
- Iterate over the range [0, 9] using a variable, say i, to check if K has any digit with more occurrences than in N. If M2[i] > M1[i], then print N and return.
- Again, iterate over the range [0, 9] using a variable i to check if K contains only 1 distinct digit. If M2[i] is the same as length(K), then print “-1” and return.
- For all other cases, sort N in decreasing order and then print N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find a permutation of// number N such that the number K does// not appear as a subsequence in Nvoid findArrangement(string n, string k){ // Stores frequency of digits of N unordered_map<char, int> um1; for (int i = 0; i < n.size(); i++) { um1[n[i]]++; } // Stores frequency of digits of K unordered_map<char, int> um2; for (int i = 0; i < k.size(); i++) { um2[k[i]]++; } // Check if any digit in K has // more occurrences than in N for (int i = 0; i <= 9; i++) { char ch = '0' + i; // If true, print N and return if (um2[ch] > um1[ch]) { cout << n; return; } } // Check if K contains only a // single distinct digit for (int i = 0; i <= 9; i++) { char ch = '0' + i; // If true, print -1 and return if (um2[ch] == k.size()) { cout << -1; return; } } // For all other cases, sort N // in decreasing order sort(n.begin(), n.end(), greater<char>()); // Print the value of N cout << n;}// Driver Codeint main(){ string N = "93039373637", K = "339"; // Function Call findArrangement(N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find a permutation of// number N such that the number K does// not appear as a subsequence in Nstatic void findArrangement(String n, String k){ // Stores frequency of digits of N HashMap<Character,Integer> um1 = new HashMap<Character,Integer>(); for (int i = 0; i < n.length(); i++) { if(um1.containsKey(n.charAt(i))) { um1.put(n.charAt(i), um1.get(n.charAt(i))+1); } else { um1.put(n.charAt(i), 1); } } // Stores frequency of digits of K HashMap<Character,Integer> um2 = new HashMap<Character,Integer>(); for (int i = 0; i < k.length(); i++) { if(um2.containsKey(k.charAt(i))){ um2.put(k.charAt(i), um2.get(k.charAt(i))+1); } else{ um2.put(k.charAt(i), 1); } } // Check if any digit in K has // more occurrences than in N for (int i = 0; i <= 9; i++) { char ch = (char) ('0' + i); // If true, print N and return if (um2.containsKey(ch) && um1.containsKey(ch) && um2.get(ch) > um1.get(ch)) { System.out.print(n); return; } } // Check if K contains only a // single distinct digit for (int i = 0; i <= 9; i++) { char ch = (char) ('0' + i); // If true, print -1 and return if (um2.containsKey(ch) && um2.get(ch) == k.length()) { System.out.print(-1); return; } } // For all other cases, sort N // in decreasing order n = sortString(n); // Print the value of N System.out.print(n);}static String sortString(String inputString) { // convert input string to char array char tempArray[] = inputString.toCharArray(); // sort tempArray Arrays.sort(tempArray); // return new sorted string return new String(new StringBuffer(new String(tempArray)).reverse()); } // Driver Codepublic static void main(String[] args){ String N = "93039373637", K = "339"; // Function Call findArrangement(N, K);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find a permutation of# number N such that the number K does# not appear as a subsequence in Ndef findArrangement(n, k) : # Stores frequency of digits of N um1 = dict.fromkeys(n, 0); for i in range(len(n)): um1[n[i]] += 1; # Stores frequency of digits of K um2 = dict.fromkeys(k, 0); for i in range(len(k)) : um2[k[i]] += 1; # Check if any digit in K has # more occurrences than in N for i in range(10) : ch = chr(ord('0') + i); if ch in um2 : # If true, print N and return if (um2[ch] > um1[ch]) : print(n, end = ""); return; # Check if K contains only a # single distinct digit for i in range(10) : ch = chr(ord('0') + i); if ch in um2 : # If true, print -1 and return if (um2[ch] == len(k)) : print(-1, end = ""); return; # For all other cases, sort N # in decreasing order n = list(n) n.sort(reverse = True) # Print the value of N print("".join(n));# Driver Codeif __name__ == "__main__" : N = "93039373637"; K = "339"; # Function Call findArrangement(N, K); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find a permutation of // number N such that the number K does // not appear as a subsequence in N static void findArrangement(string n, string k) { // Stores frequency of digits of N Dictionary<char, int> um1 = new Dictionary<char, int>(); for (int i = 0; i < n.Length; i++) { if(um1.ContainsKey(n[i])) { um1[n[i]]++; } else { um1[n[i]] = 1; } } // Stores frequency of digits of K Dictionary<char, int> um2 = new Dictionary<char, int>(); for (int i = 0; i < k.Length; i++) { if(um2.ContainsKey(k[i])) { um2[k[i]]++; } else { um2[k[i]] = 1; } } // Check if any digit in K has // more occurrences than in N for (int i = 0; i <= 9; i++) { char ch = (char) ('0' + i); // If true, print N and return if (um2.ContainsKey(ch) && um1.ContainsKey(ch) && um2[ch] > um1[ch]) { Console.Write(n); return; } } // Check if K contains only a // single distinct digit for (int i = 0; i <= 9; i++) { char ch = (char) ('0' + i); // If true, print -1 and return if (um2.ContainsKey(ch) && um2[ch] == k.Length) { Console.Write(-1); return; } } // For all other cases, sort N // in decreasing order n = sortString(n); // Print the value of N Console.Write(n); } static string sortString(string inputString) { // convert input string to char array char[] tempArray = inputString.ToCharArray(); // sort tempArray Array.Sort(tempArray); Array.Reverse(tempArray); // return new sorted string return new string(tempArray); } // Driver codew static void Main() { string N = "93039373637", K = "339"; // Function Call findArrangement(N, K); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach// Function to find a permutation of// number N such that the number K does// not appear as a subsequence in Nfunction findArrangement(n, k){ // Stores frequency of digits of N var um1 = new Map(); for (var i = 0; i < n.length; i++) { if(um1.has(n[i])) { um1.set(n[i], um1.get(n[i])+1); } else { um1.set(n[i], 1); } } // Stores frequency of digits of K var um2 = new Map(); for (var i = 0; i < k.length; i++) { if(um2.has(k[i])) { um2.set(k[i], um2.get(k[i])+1); } else { um2.set(k[i], 1); } } // Check if any digit in K has // more occurrences than in N for (var i = 0; i <= 9; i++) { var ch = String.fromCharCode('0'.charCodeAt(0) + i); // If true, print N and return if (um2.has(ch) && um1.has(ch) && um2.get(ch) > um1.get(ch)) { Console.Write(n); return; } } // Check if K contains only a // single distinct digit for (var i = 0; i <= 9; i++) { var ch = String.fromCharCode('0'.charCodeAt(0) + i); // If true, print -1 and return if (um2.has(ch) && um2.get(ch) == k.length) { document.write(-1); return; } } // For all other cases, sort N // in decreasing order n = sortString(n); // Print the value of N document.write(n);}function sortString(inputString) { // convert input string to char array var tempArray = inputString.split(''); // sort tempArray tempArray.sort(); tempArray.reverse(); // return new sorted string return tempArray.join('');} // Driver codewvar N = "93039373637", K = "339";// Function CallfindArrangement(N, K);// This code is contributed by itsok.</script> |
Output:
99776333330
Time Complexity: O(L*log (L)), where L is the size of the string N
Auxiliary Space: O(L)
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!
