 # SKMP - Editorial

Author: Mohamed Anany
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta

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: 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) - ROFL.begin();
int r = upper_bound(ROFL.begin(),ROFL.end(), t) - 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;
int cnt2;
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 - (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 = {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 - '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;
}
}
``````
6 Likes

If anyone wants video explanation in hindi- https://youtu.be/tH1pHf4Mw2U
BTW This question was great

Corner Test Cases-
INPUT :
6
zzzety
ze
acdeedaghfaee
eeaghfa
qwertyuioppppppoiuyt
tyuui
zaazyz
azy
jtewmpzqmscas
pqssc
zatgggg
gt

Correct OUTPUT :

tyzezz
acddeeaghfaee
eiooppppppqrttyuuiwy
aazyzz
aejmmpqssctwz
aggggtz

8 Likes

https://www.codechef.com/viewsolution/36845094
what is wrong with this solution

``````t=int(input())
for i in range(t):
string=input()
string2=input()

for j in string2[1:]:
string=string.replace(j,'',1)

string=''.join(sorted(string))
ind=string.index(string2)
while(string[ind]==string2 and ind<len(string)-1):

ind+=1

1 Like

Try this test case:

1

6 Likes

what is wrong with my code it gives wrong answer in online judges and when i take random cases it give right answer

1 Like

great video must watch

3 Likes

Try this.
1
abb
ba

Check where to insert the string, before or after the corresponding character.

6 Likes

why this one is not running

``````#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll i,j,t;string s,p,ans;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--)
{
cin>>s>>p;ans="";
map<char,int> M;
for(i='a';i<='z';i++)
M[i]=0;
for(i=0;i<s.length();i++)
M[s[i]]++;
for(i=0;i<p.length();i++)
M[p[i]]--;
for(i='a';i<='z';i++)
{
if(i==p)
{
for(j=0;j<M[i];j++)
ans+=char(i);
ans+=p;
}
else
{
for(j=0;j<M[i];j++)
ans+=char(i);
}
}
cout<<ans<<"\n";
}
}

``````

int pos = p - ‘a’ + flag;
Can anyone please explain the role of ‘pos’ in the editorial’s solution ??

I used hashing,but only one test case in subtask 1 is coming wrong.Can anyone help in finding which might be that case? code link :https://www.codechef.com/viewsolution/36711866

I am getting a WA in just one testcase in subtask 1. Can someone explain my mistake. The code is here: https://www.codechef.com/viewsolution/36467551

can anyone tell me why my solution is not working?
can you please provide me a testcase where my solution fails?
Edit: Ignore the class name its from previous solution https://www.codechef.com/viewsolution/36860669

what is wrong in this code?I am getting a WA in just one testcase in subtask 1
https://www.codechef.com/viewsolution/36593254

1 Like

Can anyone guide me on this code, why this isn’t working? I have tested for all the test cases that I could think off or found from the internet and got AC for each of them.
If you know some corner cases, please share them too. Thanks In advance.

``````import java.util.*;

import java.io.*;

public class Main {

public static void main (String[] args) {

FastScanner scanner = new FastScanner();

int t = scanner.nextInt();

while(t-- > 0) {

String s = scanner.next();

String p = scanner.next();

int[] freqRemaining = new int;

for (int i = 0; i < s.length(); i++) {

freqRemaining[s.charAt(i) - 'a']++;

}

for (int i = 0; i < p.length(); i++) {

freqRemaining[p.charAt(i) - 'a']--;

}

String res = "";

for (int i = 0; i < (int)(p.charAt(0) - 'a'); i++) {

while (freqRemaining[i] > 0) {

res += (char)(i + 'a');

freqRemaining[i]--;

}

}

if (p.length() > 1) {

if (p.charAt(1) <= p.charAt(0)){

res += p;

for (int i = 0; i < (int)(freqRemaining[p.charAt(0) - 'a']); i++) {

res += p.charAt(0);

}

}

else {

for (int i = 0; i < (int)(freqRemaining[p.charAt(0) - 'a']); i++) {

res += p.charAt(0);

}

res += p;

}

} else {

res += p;

for (int i = 0; i < (int)(freqRemaining[p.charAt(0) - 'a']); i++) {

res += p.charAt(0);

}

}

for (int i =(int)(p.charAt(0) - 'a'+ 1); i < freqRemaining.length; i++) {

while (freqRemaining[i] > 0) {

res += (char) (i + 'a');

freqRemaining[i]--;

}

}

System.out.println(res);

}

}

}

class FastScanner {

public StringTokenizer tokenizer;

public FastScanner() {

tokenizer = null;

}

public String next() {

while (tokenizer == null || !tokenizer.hasMoreTokens()) {

try {

} catch (IOException e) {

throw new RuntimeException(e);

}

}

}

public int nextInt() {

return Integer.parseInt(next());

}

public long nextLong() {

return Long.parseLong(next());

}

public double nextDouble() {

return Double.parseDouble(next());

}

public String nextLine() {

try {

} catch(IOException e) {

throw new RuntimeException(e);

}

}

}``````

A Simple Solution With Python.

``````for _ in range(int(input())):
f = list(input())
s = input()
for i in s:
f.remove(i)
f.sort()
chk = f.copy()
chk.append(s)
chk.sort()
if f.count(s)>0:
ns = f.copy()
for i in range(len(f)):
if f[i] == s :
ns.insert(i, s)
break
ansns = "".join(i for i in ns)
anschk = "".join(i for i in chk)
print(min(ansns, anschk))
else:
print(*chk, sep="")``````

https://www.codechef.com/viewsolution/36840205

any suggestions why W.A ?

nice

Hi ,
i have tried similar logic which is explained in the editorial but still i am getting wrong answer