I am getting correct output but my submission shows wrong

I have given this solution in july long challenge
link of my solution: https://www.codechef.com/viewsolution/36613904
here is my code

for _ in range(int(input())):
s = input()
p = input()
st = sorted(s)
st1 = ‘’

st.append(p)

for it in p:
    for te in st:
        if it == te:
            st.remove(te)
            break
        

for item in sorted(st):
    st1 += item      

print(st1)
1 Like

Hey buddy!!!
I also tried this problem and the answer should be simple.
I also get the right output but submission shows incorrect. I have checked both my code and logic 5 times.

If someone can figure this out then please help me also.

link to my code -> https://www.codechef.com/viewsolution/36564098

1 Like

@coder_indian4 @fallmount Try this testcase:
1
deadzacrosdead
dad
OUTPUT: aacdddadeeorsz
EXPECTED: aacdadddeeorsz

thanks for the test case.
I am not able to figure out what is wrong in my code.
Can you please help me with that??
Please!

While inserting the pattern in the sorted string you have to check both the cases whether to insert before the first match of p[0] p is pattern string in this case , or after the last match of p[0] in the main string .
For ex.
let the test case be
1 aabb ba
Then what you have to do is to check where to insert pattern "ba" after the b in the main string or before
b in the main string and here the optimal answer will be to insert before the b in the main string .
Hence the optimal answer of this case is abab instead of abba.

1 Like

We have to choose lexicographically smallest S.
aaakaeekmnnry < akaaaeekmnnry
and in the test case
1
deadzacrosdead
dad
aacdadddeeorsz < aacdddadeeorsz
Hope you get the logic behind this, I’m really bad at explaining
@cerr has explained it above.
You can also refer to the editorial.

@fallmount @coder_indian4
You can do the following changes in your code after your final sorted list

np=len(pattern)
flag=1
for k in range (1,np):
    if(p[k]<p[0]):
        flag=0
        break
    if(p[k]>p[0])
        break

Now if flag==1 then your codes will work fine since the sorted list will give the expected output.
For flag equals zero,

#Lets say s is your final list after sorting
if (flag==0):
   pos=0
   for i in range(0,len(s)):
      if (s[pos] == p[0]):
         index = s.index[p]
         s[pos],s[index] = s[index],s[pos]
         #swapping pattern with first occurance of p[0]

1 Like

@zacros thanks for the help buddy.

now it is working :slightly_smiling_face: :slightly_smiling_face: