Given a string s of length N consisting of digits from 0 to 9. Find the lexicographically minimum sequence that can be obtained from given string s by performing the given operations:
- Selecting any position i in the string and delete the digit ‘d‘ at ith position,
- Insert min(d+1, 9) on any position in the string s.
Examples:
Input: s = ” 5217 “
Output: s = ” 1367 “
Explanation:
Choose 0th position, d = 5 and insert 6 i.e. min(d+1, 9) between 1 and 7 in string; s = ” 2167 “
Choose 0th position, d = 2 and insert 3 i.e. min(d+1, 9) between 1 and 6 in string; s = ” 1367 “Input: s = ” 09412 “
Output: s = ” 01259 “
Explanation:
Choose 1st position, d = 9 and insert 9 i.e. min(d+1, 9) at last of string; s = ” 04129 “
Choose 1st position, d = 4 and insert 5 i.e. min(d+1, 9) between 2 and 9 in string; s = ” 0 1 2 5 9 “
Approach: Implement the idea below to solve the problem:
At each position i, we check if there is any digit sj such that sj < si and j > i. As we need the lexicographically minimum string, we need to bring the jth digit ahead of ith digit. So delete the ith digit and insert min(si+1, 9) behind the jth digit. Otherwise, if no lesser digits are present ahead of ith digit, keep the digit as it is and don’t perform the operation.
Follow the below steps to implement the above idea:
- Create a suffix vector to store the minimum digit in the right part of ith position in the string.
- Run a loop from N-2 to 0 and store the minimal digit found till index i from the end. [This can be done by storing suf[i] = min( suf[i+1], s[i] ) ].
- Create a result vector that will store the digits that will be present in the final lexicographically minimum string.
- Traverse for each position from i = 0 to N-1 in the string and check if there is any digit less than the current digit (d = s[i]-‘0’) on the right side:
- If yes then push min(d+1, 9) in result.
- Else push (d) in the result.
- Sort the vector result and print the values [Because we can easily arrange them in that way as there is no constraint on how many times we can perform the operation].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to print the minimum// string after operationstring minimumSequence(string& s){ int n = s.size(); vector<int> suf(n); string sol = ""; // Storing values in suf suf[n - 1] = s[n - 1] - '0'; for (int i = n - 2; i >= 0; i--) suf[i] = min(suf[i + 1], s[i] - '0'); // Storing values of final sequence // after performing given operation vector<int> res; for (int i = 0; i < n; i++) { // If smaller element is present // beyond index i if (suf[i] < s[i] - '0') res.push_back(min(9, s[i] - '0' + 1)); else res.push_back(s[i] - '0'); } // Sort the res in increasing order sort(res.begin(), res.end()); for (int x : res) sol += char(x + '0'); return sol;}// Driver codeint main(){ string s = "09412"; // Function call cout << minimumSequence(s); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static String MinimumSequence(String s) { int n = s.length(); int[] suf = new int[n]; String sol = ""; // Storing values in suf suf[n - 1] = s.charAt(n - 1) - '0'; for (int i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], s.charAt(i) - '0'); // Storing values of final sequence // after performing given operation int[] res = new int[n]; for (int i = 0; i < n; i++) { // If smaller element is present // beyond index i if (suf[i] < s.charAt(i) - '0') res[i] = Math.min(9, s.charAt(i) - '0' + 1); else res[i] = s.charAt(i) - '0'; } // Sort the res in increasing order Arrays.sort(res); for (int i = 0; i < res.length; i++) { sol += res[i]; } return sol; } public static void main(String[] args) { String s = "09412"; // Function call System.out.println(MinimumSequence(s)); }}// This code is contributed by lokesh. |
Python3
# python3 code to implement the approach# Function to print the minimum# string after operationdef minimumSequence(s): n = len(s) suf = [0 for _ in range(n)] sol = "" # Storing values in suf suf[n - 1] = ord(s[n - 1]) - ord('0') for i in range(n-2, -1, -1): suf[i] = min(suf[i + 1], ord(s[i]) - ord('0')) # Storing values of final sequence # after performing given operation res = [] for i in range(0, n): # If smaller element is present # beyond index i if (suf[i] < ord(s[i]) - ord('0')): res.append(min(9, ord(s[i]) - ord('0') + 1)) else: res.append(ord(s[i]) - ord('0')) # Sort the res in increasing order res.sort() for x in res: sol += str(x) return sol# Driver codeif __name__ == "__main__": s = "09412" # Function call print(minimumSequence(s)) # This code is contributed by rakeshsahni |
C#
//c# code implementationusing System;using System.Linq;public class GFG { static string MinimumSequence(string s) { int n = s.Length; int[] suf = new int[n]; string sol = ""; // Storing values in suf suf[n - 1] = s[n - 1] - '0'; for (int i = n - 2; i >= 0; i--) suf[i] = Math.Min(suf[i + 1], s[i] - '0'); // Storing values of final sequence // after performing given operation int[] res = new int[n]; for (int i = 0; i < n; i++) { // If smaller element is present // beyond index i if (suf[i] < s[i] - '0') res[i] = Math.Min(9, s[i] - '0' + 1); else res[i] = s[i] - '0'; } // Sort the res in increasing order Array.Sort(res); for (int i=0;i<res.Length;i++){ sol += res[i].ToString(); } return sol; } static void Main(string[] args) { string s = "09412"; // Function call Console.WriteLine(MinimumSequence(s)); }}// code by ksam24000 |
Javascript
// Javascript code to implement the approach// Function to print the minimum// string after operationfunction minimumSequence(s){ let n = s.length; let suf =new Array(n); let sol = ""; // Storing values in suf suf[n - 1] = parseInt(s[n - 1]); for (let i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], parseInt(s[i])); // Storing values of final sequence // after performing given operation let res= []; for (let i = 0; i < n; i++) { // If smaller element is present // beyond index i if (suf[i] < parseInt(s[i])) res.push(Math.min(9, parseInt(s[i]) + 1)); else res.push(parseInt(s[i])); } // Sort the res in increasing order res.sort(); for (let x=0 ; x<res.length; x++) sol+=res[x]; return sol;}// Driver code let s = "09412"; // Function call document.write(minimumSequence(s)); |
Output
01259
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Related Articles:
- Introduction to String – Data Structure and Algorithm Tutorials
- Introduction to Greedy Algorithm – Data Structures and Algorithm Tutorials
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!
Share your thoughts in the comments
