Problem
Given a string s such that, s ∈ merge(reverse(A), shuffle(A)) for some string A, find the lexicographically smallest A.
Input
A single line containing the string s.
Output
Find and return the string which is the lexicographically smallest valid A
Constraints
- 1 <= |s| ≤ 10000
- s contains only lower-case English letters, ascii[a-z]
Sample Input
eggegg
Sample Output
egg
Solution
Approach: Greedy Algorithm
Given S, We want to find the lexicographically smallest A such that:
S ∈ merge(reverse(A), shuffle(A))
Now this could also be written as:
S ∈ merge(reverse(A), shuffle(A))
<==>
reverse(S) ∈ merge(A, shuffle(A))
Since constraints allow us to use a O(n2) solution. We could use a brute force greedy approach.
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | //// main.cpp// Reverse Shuffle Merge//// Created by Himanshu on 23/03/22.//#include <iostream>#include<vector>#include<string>#include<algorithm>#include <cstring>#define MAX_SIZE 26using namespace std;int main() { string s,s1; int n, p, ok; int *count = new int[MAX_SIZE](); int *passcount = new int[MAX_SIZE](); int *acount = new int[MAX_SIZE](); char ans[10000]; cin>>s; n = (int) s.size(); for (int i=0; i<n; i++) { count[s[i]-'a']++; } reverse (s.begin(), s.end()); for (int l=0; l<n/2; l++) { //Checking every possible char(a-z) for position l //in required string for (int j=0; j<26; j++) { if (acount[j] < count[j]/2) { ans[l] = (char)(j + 'a'); } acount[j]++; p = 0; for (int i=0; i<n; i++) { if (ans[p] == s[i]) { p++; if (p > l) { break; } } passcount[s[i]-'a']++; } ok = 1; for (int k=0; k<26; k++) { //If remaining number of a particular char(a-z) //is larger than the required number, reject the current char for //position l if (count[k]/2 < (passcount[k] - acount[k])) { ok = 0; break; } } //resetting passcount for checking the number //of types a char(a-z) is used memset(passcount, 0, MAX_SIZE*sizeof(int)); //current char is accepted for position l if (ok) { break; } else { //rejecting the current char for position l acount[j]--; } } } ans[n/2] = NULL; cout<<ans<<endl; return 0;} |
Time complexity: O(n2)