SKMP - Editorial

PROBLEM LINK:

Division 1
Division 2

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;
    }
}  
6 Likes

If anyone wants video explanation in hindi- Code Chef : Smallest KMP Problem | August Long Challenge Solution In Hindi with Explanation - YouTube
BTW This question was great

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

Compare your output with this
Correct OUTPUT :

tyzezz
acddeeaghfaee
eiooppppppqrttyuuiwy
aazyzz
aejmmpqssctwz
aggggtz

10 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[0])
    while(string[ind]==string2[0] and ind<len(string)-1):
  
        ind+=1
    addstr=string[ind-1:]

    print(string[:ind-1]+addstr.replace(string2[0],string2,1))
1 Like

Try this test case:

1
madammadam
madam

Your code outputs aadmmmadam

answer is aadmadammm

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

Correct Answer : bab
Your Answer : bba

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[0])
            {
                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[0] - ‘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 :CodeChef: Practical coding for everyone

I am getting a WA in just one testcase in subtask 1. Can someone explain my mistake. The code is here: CodeChef: Practical coding for everyone
Thanks in advance

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 :smiley:
https://www.codechef.com/viewsolution/36860669

what is wrong in this code?I am getting a WA in just one testcase in subtask 1
it is running for all subtasks and tasks except one.
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[26];

                

                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 BufferedReader reader;

    public StringTokenizer tokenizer;

    public FastScanner() {

        reader = new BufferedReader(new InputStreamReader(System.in), 32768);

        tokenizer = null;

    }

    public String next() {

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

            try {

                tokenizer = new StringTokenizer(reader.readLine());

            } catch (IOException e) {

                throw new RuntimeException(e);

            }

        }

        return tokenizer.nextToken();

    }

    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 {

            return reader.readLine();

        } 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])>0:
        ns = f.copy()   
        for i in range(len(f)):
            if f[i] == s[0] :
                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
Can you any one please check below answer
https://www.codechef.com/viewsolution/36861968

it will be helpful to me understand my mistakes

Thanks

I have written a solution by calculating frequency of characters but it didn’t work. Can someone figure it out it would be very helpful.
https://www.codechef.com/viewsolution/36862964