Given a string S of size N, having lowercase alphabets, the task is to find the lexicographically minimum string after moving a subsequence to the end of the string only once.
Example:
Input: N = 3, S = “asa”
Output: aas
Explanation: The optimal subsequence is “s”.
Removed, and added at last. Hence the final string is ‘aa’ + ‘s’ =’aas’Input: N = 7, S = “fabccac”
Output: aacfbcc
Explanation: The optimal subsequence is “fbcc”.
Any other subsequence will not give the minimum
Hence the final string is ‘aac’ + ‘fbcc’ = ‘aacfbcc’
Approach: The problem can be solved based on the following observation:
To find the lexicographically minimum string the selected subsequence should follow the pattern.
- The 1st character of the selected subsequence to be removed should be same or greater than the last character of the retaining subsequence.
- The non selected subsequence shall form a non-decreasing sequence.
Follow the steps to solve the problem:
- Initialize a boolean array to maintain the position of characters if included in the subsequence to be shuffled or not.
- Maintain a stack for finding non-decreasing subsequence of retaining characters
- At every character, pop all characters greater than the current character from the stack.
Below is the implementation for the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find lexicographically minimumstring LexMin(int n, string s){ // Boolean array for storing positions // and frequencies vector<int> last(26, -1); for (int i = 0; i < n; i++) { last[s[i] - 'a'] = i; } int dig = 0; int mx = 26; // ans for storing resultant string // ans1 for leftout and ans2 for picked up string ans = s, ans1, ans2; for (int i = 0; i < n; i++) { // For every i we will find its // last occurrence last[dig] while (dig < 26 && i > last[dig]) dig++; if (dig == mx) { string ans3 = ans2, ans4; for (int j = i; j < n; j++) { // Adding the character if (s[j] == ('a' + mx)) { ans4.push_back(s[j]); } else { ans3.push_back(s[j]); } } // Remove the other half and // store the substring upto i ans2 += s.substr(i); // Find out the minimum // and put it into ans ans = min(ans, ans1 + min(ans2, ans4 + ans3)); break; } else if (dig > mx) { ans = min(ans, ans1 + ans2 + s.substr(i)); break; } // ans1 holds value retaining values if (s[i] == ('a' + dig)) { ans1.push_back(s[i]); } else { if (mx == 26) mx = (s[i] - 'a'); ans2.push_back(s[i]); } // Corner cases if (i == n - 1) ans = min(ans, ans1 + ans2); } // Return the ans return ans;}// Driver codeint main(){ int N = 3; string s = "asa"; // Function call cout << LexMin(N, s) << endl; return 0;} |
Java
import java.util.Arrays;class Main { // Function to find lexicographically minimum static String LexMin(int n, String s) { // Boolean array for storing positions // and frequencies int[] last = new int[26]; Arrays.fill(last, -1); for (int i = 0; i < n; i++) { last[s.charAt(i) - 'a'] = i; } // ans for storing resultant string // ans1 for leftout and ans2 for picked up int dig = 0; int mx = 26; // ans for storing resultant string // ans1 for leftout and ans2 for picked up String ans = s, ans1 = "", ans2 = ""; for (int i = 0; i < n; i++) { // For every i we will find its // last occurrence last[dig] while (dig < 26 && i > last[dig]) { dig++; } if (dig == mx) { String ans3 = ans2, ans4 = ""; for (int j = i; j < n; j++) { if (s.charAt(j) == ('a' + mx)) { ans4 += s.charAt(j); } else { ans3 += s.charAt(j); } } // Remove the other half and // store the substring upto i ans2 += s.substring(i); // Find out the minimum // and put it into ans ans = min(ans, ans1 + min(ans2, ans4 + ans3)); break; } else if (dig > mx) { ans = min(ans, ans1 + ans2 + s.substring(i)); break; } // ans1 holds value retaining values if (s.charAt(i) == ('a' + dig)) { ans1 += s.charAt(i); } else { if (mx == 26) { mx = (s.charAt(i) - 'a'); } ans2 += s.charAt(i); } // Corner cases if (i == n - 1) { ans = min(ans, ans1 + ans2); } } return ans; } static String min(String a, String b) { return a.compareTo(b) < 0 ? a : b; }// Driver code public static void main(String[] args) { int N = 3; String s = "asa"; System.out.println(LexMin(N, s)); }}//This code is contributed by Edula Vinay Kumar Reddy |
Python3
# Python3 code for the above approach# Function to find lexicographically minimumdef LexMin(n, s) : # Boolean array for storing positions # and frequencies last = [-1] * 26; for i in range(n) : last[ord(s[i]) - ord('a')] = i; dig = 0; mx = 26; # ans for storing resultant string # ans1 for leftout and ans2 for picked up ans = s; ans1,ans2 = "",""; for i in range(n) : # For every i we will find its # last occurrence last[dig] while (dig < 26 and i > last[dig]) : dig += 1; if (dig == mx) : ans3 = ans2; ans4 = ""; for j in range(1, n) : # Adding the character if (ord(s[j]) == (ord('a') + mx)) : ans4 += s[j] ; else : ans3 += s[j]; # Remove the other half and # store the substring upto i ans2 += s[:i]; # Find out the minimum # and put it into ans ans = min(ans, ans1 + min(ans2, ans4 + ans3)); break; elif (dig > mx) : ans = min(ans, ans1 + ans2 + s[:i]); break; # ans1 holds value retaining values if (ord(s[i]) == (ord('a') + dig)) : ans1 += s[i]; else : if (mx == 26) : mx = (ord(s[i]) - ord('a')); ans2 += s[i]; # Corner cases if (i == n - 1) : ans = min(ans, ans1 + ans2); # Return the ans return ans;# Driver codeif __name__ == "__main__" : N = 3; s = "asa"; # Function call print(LexMin(N, s)); # This code is contributed by AnkThon |
C#
// C# code for the above approachusing System;class Program{ static string LexMin(int n, string s) { // Boolean array for storing positions // and frequencies int[] last = new int[26]; for (int i = 0; i < 26; i++) { last[i] = -1; } for (int i = 0; i < n; i++) { last[s[i] - 'a'] = i; } int dig = 0; int mx = 26; // ans for storing resultant string // ans1 for leftout and ans2 for picked up string ans = s; string ans1 = "", ans2 = ""; for (int i = 0; i < n; i++) { // For every i we will find its // last occurrence last[dig] while (dig < 26 && i > last[dig]) { dig++; } if (dig == mx) { string ans3 = ans2; string ans4 = ""; for (int j = 1; j < n; j++) { // Adding the character if (s[j] == 'a' + mx) { ans4 += s[j]; } else { ans3 += s[j]; } } // Remove the other half and // store the substring upto i ans2 += s.Substring(0, i); // Find out the minimum // and put it into ans ans = Min(ans, ans1 + Min(ans2, ans4 + ans3)); break; } else if (dig > mx) { ans = Min(ans, ans1 + ans2 + s.Substring(0, i)); break; } // ans1 holds value retaining values if (s[i] == 'a' + dig) { ans1 += s[i]; } else { if (mx == 26) { mx = s[i] - 'a'; } ans2 += s[i]; } // Corner cases if (i == n - 1) { ans = Min(ans, ans1 + ans2); } } // Return the ans return ans; } static string Min(string a, string b) { if (string.Compare(a, b) < 0) { return a; } else { return b; } } static void Main(string[] args) { int N = 3; string s = "asa"; // Function call Console.WriteLine(LexMin(N, s)); }}// This code is contributed by rishabmalhdijo |
Javascript
<script>// JavaScript code for the above approach// Function to find lexicographically minimumfunction LexMin(n,s){ // Boolean array for storing positions // and frequencies let last = new Array(26).fill(-1); for (let i = 0; i < n; i++) { last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i; } let dig = 0; let mx = 26; // ans for storing resultant string // ans1 for leftout and ans2 for picked up let ans = s, ans1 ="" , ans2 = ""; for (let i = 0; i < n; i++) { // For every i we will find its // last occurrence last[dig] while (dig < 26 && i > last[dig]) dig++; if (dig == mx) { let ans3 = ans2, ans4; for (let j = 1; j < n; j++) { // Adding the character if (s.charCodeAt(j) == ('a'.charCodeAt(0) + mx)) { ans4 += s[j]; } else { ans3 += s[j]; } } // Remove the other half and // store the substring upto i ans2 += s.substring(0,i); // Find out the minimum // and put it into ans ans = ans1; if(ans2 > ans4 + ans3) ans2 = ans4 + ans3; if(ans > ans2) ans = ans2; break; } else if (dig > mx) { if(ans > ans1 + ans2 + s.substring(0,i)) ans = ans1 + ans2 + s.substring(0,i) break; } // ans1 holds value retaining values if (s.charCodeAt(i) == ('a'.charCodeAt(0) + dig)) { ans1 += s[i]; } else { if (mx == 26) mx = (s.charCodeAt(i) - 'a'.charCodeAt(0)); ans2 += s[i]; } // Corner cases if (i == n - 1){ if(ans > ans1 + ans2) ans = ans1 + ans2; } } // Return the ans return ans;}// Driver codelet N = 3;let s = "asa";// Function calldocument.write(LexMin(N, s),"</br>");// This code is contributed by shinjanpatra</script> |
Output
aas
Time Complexity: O(N)
Auxiliary Space: O(N)
