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
//
// 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 26
using 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)