PROBLEM LINK:
Author: Mohamed Anany
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta
DIFFICULTY:
Easy
PREREQUISITES:
Hashing, Observation
PROBLEM:
You are given two strings S and P of lowercase English characters. You have permuted the characters of string S, let’s call it to string T such that:
- P is a substring T.
- T should be lexicographically smallest possible.
Print the string T.
Note: Test data is designed such that there exist at least one such T for which P is the substring of T where T is the anagram of S.
QUICK EXPLANATION:
We can easily solve the task in two different cases:
-
If P_i > P_{i-1} for any valid i(> 0, considering 0-based indexing and P_j == P_{j-1} for j < i ) or P_i == P_{i-1} for each valid i(> 0), then we need to find all the extra characters in S which are not contributing in P and append them at the start of P if the character is smaller or equal to the P_0 else append them at the end of P.
-
else we need to find all the extra characters in S which are not contributing in P and append them at the start of P if the character is smaller then P_0 else append them at the end of P.
EXPLANATION:
- What is contributing in P means?
- Some of the characters of string S is used to form P so we are calling a character based on whether it is contributing to P or not.
It is easy to see that we should care only which are not contributing into P and final string T should be constructed by appending some of them before P and some of them after P.
Let’s create a frequency array f of size 26 which takes record of these extra characters and as we only have lowercase english alphabets so we are mapping them with 0 to 26 as a to z.
Now, If P_i > P_{i-1} for any valid i(> 0, considering 0-based indexing and P_j == P_{j-1} for j < i ) or P_i == P_{i-1} for each valid i(> 0), then all the characters which are not contributing in P from a to P_0 should append at the start of P and rest are at the end of P. This can be easily tracked by frequency array f.
Else we know that we should not place the characters equal to P_0 in the start of string P as string P contains some character which is smaller than P_0 in somewhere which can do better if we place these characters at the end of string P.
For example: If S is equal to “bab” and P is equal to “ba” then T should be “abb” and If S is equal to “baa” and P are equal to “ab” then T should be “aab”.
TIME COMPLEXITY:
TIME: O(N)
SPACE: O(26)
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using uint = unsigned int;
using db = long double;
using ii = pair<int,int>;
const int N =1e5+5, MOD = 1e9 + 7;
string s, t;
vector<int> getFreq(string s){
vector<int>ret(26, 0);
for(auto c : s)
ret[c-'a']++;
return ret;
}
vector<int> operator - (vector<int> x, vector<int> y){
vector<int>ret(26);
for(int i = 0; i < 26; i++)
ret[i] = x[i] - y[i];
return ret;
}
string ins(string x, string y, int idx){
return x.substr(0,idx) + y + x.substr(idx);
}
int32_t main(){
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
int tst; cin >> tst;
while(tst--){
cin >> s >> t;
vector<int> lft = getFreq(s) - getFreq(t);
string ROFL = "";
for(int i = 0; i < 26; i++)
for(int j = 0; j < lft[i]; j++)
ROFL.push_back('a' + i);
int l = lower_bound(ROFL.begin(),ROFL.end(), t[0]) - ROFL.begin();
int r = upper_bound(ROFL.begin(),ROFL.end(), t[0]) - ROFL.begin();
if(ins(ROFL,t,l) < ins(ROFL,t,r))
cout << ins(ROFL,t,l) << '\n';
else
cout << ins(ROFL,t,r) << '\n';
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define mp make_pair
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const int MAX = 500000;
int cnt[256];
int cnt2[256];
int main() {
int T;
cin >> T;
while(T--)
{
memset(cnt, 0 , sizeof cnt);
memset(cnt2 , 0 , sizeof cnt2);
string S , P;
cin >> S >> P;
int ptrP = 0;
for(auto x : S)
cnt[x]++;
for(auto x : P)
cnt2[x]++;
int inc = 0;
for(int i = 0; i < sz(P) - 1; i++)
{
if(P[i] < P[i + 1])
inc = 1;
if(P[i] > P[i + 1])
inc = -1;
if(inc) break;
}
char to = P[0] - (inc != 1);
for(char i = 'a'; i <= to; i++)
for(int x = 0; x < cnt[i] - cnt2[i]; x++)
cout << i;
cout << P;
for(char i = to + 1; i <= 'z'; i++)
for(int x = 0; x < cnt[i] - cnt2[i]; x++)
cout << i;
cout << endl;
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
string s,p;
cin >> s >> p;
int cnt[26] = {0};
for(char i:s) cnt[i-'a']++;
for(char i:p) cnt[i-'a']--;
int flag = 1;
for(int i=1;i<p.size();i++)
{
if(p[i] == p[i-1])
continue;
if(p[i] < p[i-1])
flag = 0;
break;
}
int pos = p[0] - 'a' + flag;
for(int i=0;i<pos;i++)
{
while(cnt[i] > 0)
{
char c = 'a' + i;
cout << c;
cnt[i]--;
}
}
cout << p;
for(int i=pos;i<26;i++)
{
while(cnt[i] > 0)
{
char c = 'a' + i;
cout << c;
cnt[i]--;
}
}
cout << endl;
}
}
