# Append and Delete

# Append and Delete

ngtzeyang1994 + 49 comments Let me do my best to explain the different cases that could happen:

int commonLength = 0; for (int i=0; i<java.lang.Math.min(s.length(),t.length());i++){ if (s.charAt(i)==t.charAt(i)) commonLength++; else break; } //CASE A if((s.length()+t.length()-2*commonLength)>k){ System.out.println("No"); } //CASE B else if((s.length()+t.length()-2*commonLength)%2==k%2){ System.out.println("Yes"); } //CASE C else if((s.length()+t.length()-k)<0){ System.out.println("Yes"); } //CASE D else{ System.out.println("No"); }

CASE A:

What this case is finding is if k is bigger than the difference in length of the two strings.

example: s = "123456789", t = "1", k = 5

in this case, you definitely need a bigger k to transform s to t or vice versa, therefore you reject any such cases.

Case B:

now that the case has passed A, we can say that the total number of letters required to change is less than or equal to k.

however the next problem comes because the question specified that exactly k moves must be done, no more no less. this leads to an example whereby:

s = "010101", t = "01010", k = any EVEN number

OR

s = "010101", t = "010101", k = any ODD number

from these two examples you can see that only if k is odd/even matches the odd/even of number of different digits will such cases pass.

Case C:

However there is a way to overcome this odd/even problem if you are able to completely delete away one string as a deletion action on an empty string results in another empty string.

Example: s = '1' t = '101' k = 5

in this case, to get a S from T you could do delete-delete-delete-delete-add(1) and you will satisfy the condition.

Case D:

all other cases will fail the test

Hope i helped

withasingle_t + 0 comments Nice algo!

tanuj_kapoor15 + 1 comment I'm sorry I might be wrong but what if I append by a null character? I mean in case B where t="01010" let's assume k=7 what if I just append t by a null character and then append it with a 1, it would pass the test case, right?

lemuel_dulfo + 1 comment You are not allowed to append a null character. The problem clearly states that you can perform two operations per "step", and the first operation is:

- Append a lowercase English alphabetic letter to the end of the string.

tanuj_kapoor15 + 1 comment Thanks for clearing it out.

madhu703 + 0 comments Can you explain case B with one more example . I didn't get it exactly how it works.

alexermashev + 7 comments Yor explanation is hard to understand, check a look at me code. I think it easy to understand

function isItPossibleToModify($s, $t, $k) { $sLength = strlen($s); $tLength = strlen($t); if ($sLength < $tLength) { return ($tLength - $sLength) % 2 == 0; } $commonPrefix = 0; // find a largest common prefix between s and t for ($i = 0; $i < min($sLength, $tLength); $i++) { if ($s[$i] != $t[$i]) { break; } $commonPrefix++; } $needToProcess = ($tLength - $commonPrefix) + ($sLength - $commonPrefix); return $needToProcess <= $k; }

Vishnu_Vijayan + 10 comments What about for this testcase ?

abc abc 1

It gives Yes. Shouldn't the answer be No.

riyadali + 0 comments Along the lines of what was previously mentioned ...

---> note prefixLen contains the length of the matching prefix in both strings

`int minOps=(schar.length-prefixLen)+(tchar.length-prefixLen); if (k>=minOps) { // check if you have sufficient operations to // remove first string entirely and the replace it // with the second string if (k>=(schar.length+tchar.length)) System.out.println("Yes"); else { // cannot replace first string totally so extra available // ops must be an even multiple allowing you to // replace portions of the prefix that both strings have // in common if ((k-minOps)%2==0) System.out.println("Yes"); else System.out.println("No"); } } else { System.out.println("No"); }`

jaywhy13 + 2 comments I'm not clear as to why the answer for this test case isn't Yes and then 0 ops.

rjain90 + 1 comment It's No because it has to be exactly K moves, neither less nor more.

mohammedjunaid + 1 comment [deleted]nitinshaily0 + 0 comments python soln:

def appendAndDelete(s, t, k):

`flag=0 while(k): if len(s)==0: k=k-len(t) if k>=0: flag=1 break else: break elif s in t: if s[0]==t[0]: if len(t)-len(s)==k: flag=1 break elif len(t)-len(s)<k: if len(s)%2==len(t)%2: #if both are even or odd if k%2==0: flag=1 else: if k%2!=0: flag=1 else: break s=s[:-1] k-=1 if flag==0: return 'No' return 'Yes'`

edrouwendaal + 0 comments you can use an unlimited number of deletions on an empty string

ashitpanda2107 + 0 comments Of course the answer should be NO :)

tarunkarang + 0 comments you have one step and its nessecary to be performed, so if you add a char it wont be the same, similarly if you remove it wont be same

kininge007 + 0 comments it can solve in 0 steps so, Yes

sakshamgoyalswm + 0 comments int i=0,j=0; while(

*(s+i)==*(t+i) && *(s+i)!='\0' && *(t+i)!='\0') { i++; } int sa=strlen(s); int ta=strlen(t); j=sa-i+ta-i; static char yes[]="Yes"; static char no[]="No"; if(k`else return yes;`

neha86_arora + 0 comments ya..Answer should be No..

gtanishka8 + 0 comments Exactly!

yogeshverma28698 + 0 comments # include

using namespace std; int main(){ string s,t; int a,b; cin>>s>>t; cin>>a; int m = s.length(); int n = t.length(); int i = 0,j = 0; while(s[i++] == t[j++]); b = i-1; if(a < (m-b) + (n-b)) cout<<"No"; else{ if(m == n && a >= m*2) cout<<"Yes"; else if((m-b) + (n-b) == a) cout<<"Yes"; else cout<<"No"; } //cout<

sharadhardikar + 1 comment k is 7 (not 1) in this test case. I too however wonder at the answer 'Yes".

hnairiareg + 0 comments yeah 3 times add a letter 3 times remove you get 1 left in case 5 however you also are having 1 left but the answer is NO HOW?!

mukeshbhakuni590 + 0 comments didn't understood your code but it works . how did the (return (sLength) % 2 == 0;) condition works . can u please explain

_silent_ + 1 comment What about for this test case? peek seeker 3 It should give you no as answer But running your code against this test case will give Yes

if (tLength) { return (sLength) % 2 == 0; }

if(4<6){ return(6-4)%2==0 gives yes But can't be converted }

sharadhardikar + 0 comments my code returns "No" to this peek seeker 3

but returns "No" to the testcase in question i.e. abc abc 7 (I think k = 1 in original question is either a typo or the question has been changed over the period. In any case answer should be "No" in both scenarios.)

fran_rabljenovi1 + 0 comments At k you need to check if the remaining steps can cross out each other.

sumuduliyanage + 1 comment y yu 2 For this,what would be the answer? In test cases it is given as "No",but I feel the answer is "Yes"

prajwalcs + 1 comment Yes,even i got that test case wrong The answer should be Yesbut they have given it as No

kumarakash007 + 2 comments It's a correct case. You have to replace the word by exact numbers of steps and not by less or equal steps. You can't do that in 2 step here.

maka_kc1996 + 0 comments But it was stated in the problem description that if there are extra steps they can be eliminated.

m_berkancetin + 1 comment Even in the description it is given as an example:

aba

aba

7

"Yes"

Apparently it is a mistake

rudranshjani18 + 1 comment remove aba->3 remove from Empty ->1 append aba->3

Answer "YES"

TestCase is Correct

sunkisrinivas005 + 1 comment why do we need another opertion on empty string ?

raiden612 + 0 comments Since you need to make exactly

`k`

moves, you have 2 options.After arriving at a common phrase between

`s`

and`t`

perform add-delete pairs to satisfy "even" number of additional moves.After emptying the string any number of additional moves can be made.

Additional deletes on empty string does not change the string but consumes the move, allowing you to make the change from

`abc`

to`abc`

in any moves more than 6.`k`

values 1, 3, 5 should return`No`

.Hope this helps.

sudeepharry357 + 0 comments what is that dollar like thing?? please explain

firozbhaikardar1 + 0 comments `if (`$sLength < $`tLength) { return (`$tLength - $`sLength) % 2 == 0; }`

`can u explain`

sharwinsharwi + 0 comments this is the correct one CASE D: else if((s.length()+t.length()-k)>1)

ram_24 + 0 comments [deleted]jjpatel361 + 0 comments I didn't understand why you need

`2*commonLength`

in your first condition.`Kmin = commonLength + delete_bigger_word + add_small_word`

`delete_bigger_word`

= number of delete operations required in longer word.`add_small_word`

= number of addition operations required in smaller word to be equal to larger_wordRushabhPatel + 0 comments Could you explain Case B again ?

renatodepaiva + 0 comments Thank you so much for showing the solution and explaining it in such a clear way!

m4manishpushkar + 0 comments Bhaisaaaab you nailed it.

The_code_shinobi + 0 comments Brilliant solution and thanks for the lucid explanation.

nammivasant + 0 comments Can you explain case 2 one more time with different example?

Specter123 + 0 comments nice

sharmaspg + 0 comments nice explaination !but i need come to this logic myself .how do i do that ?

mukeshbhakuni590 + 0 comments nice explanation ... ! cleared my doubt

pappasbrent + 0 comments Thank you! I almost had it, but my logic was convoluted and confusing. Your method of first finding the index at which the two strings start to differ and building off of that is much cleaner

harishamarnath21 + 1 comment may i know why this test case should return "No" uoiauwrebgiwrhgiuawheirhwebvjforidkslweufgrhvjqasw vgftrheydkoslwezxcvdsqjkfhrydjwvogfheksockelsnbkeq 100 its add 50 and remove 50 right?

Lalchetaketan022 + 1 comment string length are not 50 for both. First one has 51 characters and second one has 50. so, it's required to have 51+50 = 101 not 100

eabarry + 0 comments Both strings are length 50, so k=100 should produce a "Yes".

singhal_purvi14 + 0 comments I want to know how you think of this approach. How do you start thinking this problem?

SL170031111 + 0 comments nice expalnation thank u

kishoresaldanha + 0 comments You may need to add another case if len(s)==len(t) and k=2*commonLength+1 right after case A

DarkSilence + 0 comments Example: s = 'ABCD' t = 'BCD' k = 1 return "No" ???

JJJason + 0 comments I think case A should be 'k is smaller than the difference in length of the two strings.'

jnrdn0011 + 0 comments Thank you.

Sithlords1999 + 0 comments suppose s="ash" t="ashley" ,k=10; according to algo ans is no but if we do 4 delete operations on s and 6 append operation,then we can convert s into t.

aayushsugandhi11 + 0 comments how did u paste this solution . i want to post my solution in python

[deleted] + 0 comments [deleted]ghassan_karwchan + 0 comments Nice explenation. Without your explenation, I could never got it. Their description for the problem is lacking enough explanation. They should emphacize on that the moves should match "Exactly" k.

hardik_dadga + 0 comments In the example of case C, why do you say "to get s from t you can......" When the PS stated is "Given an integer, k, and two strings, and , determine whether or not you can convert

**'s'**to**'t'**by performing exactly 'k' of the above operations on 's'. If it's possible, print Yes. Otherwise, print No."_JXD_ + 1 comment When case 3 occurs the expression "(s.length()+t.length()-k) < 0" will always be false using C++. That is because you are substracting a signed integer from an unsigned integer, which will result in an unsigned integer and thus will never be less than 0. To correct this, you can write: "(int(s.length()+t.length())-k)". I spent half an hour figuring this out...

raiden612 + 0 comments Or make it

s.length()+t.length() < k

to avoid explicit casting

mehul_sachdeva7 + 2 comments my js approach, quite different but almost same

function appendAndDelete(s, t, k) { var end = 0; for (var i = 0; i < Math.min(t.length, s.length); i++) { if (s[i] == t[i]) { end++; } else { break; } } var maxIter = s.length + t.length; var minIter = maxIter - (2 * end); if ((k >= minIter) & ((k - minIter) % 2 == 0)) { return "Yes"; } else if (k >= maxIter) { return "Yes"; } else { return "No"; } }

sam____ + 0 comments what if (k - minIter) % 2 != 0) but (k - minIter) >= 2*end )

roshanrzn96 + 0 comments worked as charm for all test cases

if someone has some uncleared test cases even after the above code then try applying this code :

`var l1=s.length; var l2=t.length; var count=0; for(let i=0;i<l1;i++){ if(s[i]==t[i]){ count++; } else{ break; } } if(parseInt(l1-count)+parseInt(l2-count)<=k){ if(parseInt(l1)+parseInt(l2)<=k){ return "Yes"; } else if((k-(parseInt(l1-count)+parseInt(l2-count)))%2==0){ return "Yes"; } else return "No"; } else{ return "No"; }`

asad70161 + 1 comment Your codefailed at this test case y yu 2 it gives yes, answer is no

almagician + 1 comment My code also failed on this case. What is the issue? It looks like it shoud be yes.

Also this case: abcd abcdert 10

Mine is giving Yes, but it is wrong.

kurohashi + 2 comments Question asks "exactly k" moves, so we have to perform 2 moves here even if it becomes "yu" in first move. The second move will distort it again.

almagician + 0 comments thank you, i got it)

Ram_Babu93 + 0 comments [deleted]

arsen_budumyan + 0 comments For Case B it should be for: s = "010101", t = "01010", k = any ODD number for: s = "010101", t = "010101", k = any EVEN number

thank you for your explanation :)

prmshaw906 + 0 comments great analysis

kaman7580 + 0 comments Given that case 3 can be done, isn't case 2 redundant ?

pol_alok + 0 comments Ya good bro! it can be done by this way also ;)

static String appendAndDelete(String s, String t, int k) { int noOfOpration = s.length()+t.length(),len; if(s.length() < t.length()) len=s.length(); else len=t.length();

`for(int i=0; i<len; i++) { if(s.charAt(i)==t.charAt(i)) noOfOpration-=2; else break; } return (noOfOpration > k) ? "No" : (noOfOpration%2 == k%2) ? "Yes" : ((s.length()+t.length()-k)<0) ? "Yes" : "No"; }`

rishi_raj4662 + 0 comments [deleted]Rialakshmi + 0 comments Bravo!!

bituagarwal24 + 0 comments testcase 4 and 8 are not passing

Cyclone14089 + 0 comments nicely done

arunksapkal364 + 0 comments I think Your code is correct but in case B the example you gave is explained incorrectly. In first eg odd no of transformations are required and similarly second eg.

mishraabhishek81 + 0 comments what about this hackerha hackerrank

your code will print Yes for this but it is not done at exact k=100

are you just considering that if s can be converted to t in even number of operations for this example in 6 steps which is less than k than you can delete and append the last char until k become exact 100

sonptFX02225 + 0 comments Very outstanding! now I know how to deal it!

mbhuwaniya + 0 comments string1:-adesbghc string2:-abc steps:-5; bro this should work. but instead of "Yes" it is saying "No". It requires only 5 steps of deletion only, but your code needs 9 steps..

DONTKILLME + 0 comments If any 1 is having problem in understanding case B all he meant is as below:

eg:-

s=hackerrank

t=hackerearth

k=11

len(s)+len(t)=10+11=21

commonlenghth=6

21-2*6=21-12=9

s=hackerrank->hacker

moves performed =4

moves left=11-4=7

to make s(hacker)->t(hackerearth) we require 5 more moves to append "earth" but we have 7-5 =2 i.e we have 2 extra move so we use this move as to delete and append the same character as follows :

s=hacker->hacke->hacker->hackerearth

explanation=(original)->(deleted "r")->(appended "r")->(appended "earth")

moves=7

and hence if we had an even number we would not have been able to perform this operation the same will be the case if we had an even string and even value of k

hope my exlanation helps someone in need.

DONTKILLME + 0 comments Case B:

I wil try my level best to explain

eg:

s=hackerrank

t=hackerearth

k=11

ls=length of s =10

lt=length of t=11

ls+lt=21

commonlength=6

21-2*6=21-12=9

t=hackerrank

we use 4 moves to delete "rank"

t=hacker

we have moves=k-4=11-4=7 left

we need 5 moves to append "earth"

moves=7-5=2 left

following is the explanation we will use thise extra 2 moves

s=hacker->hacke->hacker->hackerearth

explanation=(original string)->(remove r)->(append r)->(append "earth")

moves=(7)->(6)->(5)->(0)

s=t is acheived

if k were to be an even number then this would not have been possible

it will be only possible if (ls+lt-2*commonlength) is even and k is even

hope my explanation help some one in need

theharsh + 0 comments [deleted]kumar_ak16121999 + 0 comments can you explain why this is giving "Yes" for test case aba aba 7

according to your program it should give "No"

rudranshjani18 + 0 comments abhishekmore710 + 0 comments [deleted]suswaramharshav1 + 0 comments You comment helped me a lot when I was two pints away from the score. Thanks mate.

Here I am posting my code in C++

int main() { string s; std::cin>>s;

`string t; std::cin>>t; int k; cin >> k; int cmon_len=0; while(s[cmon_len] == t[cmon_len] && cmon_len < s.size()) ++cmon_len; std::string result = "No"; //This case is for when two strings are unique if(!cmon_len) result = s.size() + t.size() <= k ? "Yes" : "No"; //This case is for when both the string size are equal bool is_same = (s.size() == cmon_len && t.size() == cmon_len); if(is_same) result = (s.size() + t.size() <= k || k > 1) ? "Yes" : "No"; auto rem_t = t.size() - cmon_len; auto rem_s = s.size() - cmon_len; if(s.size() < t.size()) result = (t.size() - s.size())%2 == k%2 ? "Yes" : "No"; else result = rem_t+rem_s <= k ? "Yes" : "No"; std::cout<<result<<std::endl; return 0;`

}

ryalman + 1 comment It should not be considered as an easy problem. I hardly solved it.

JamesCater + 0 comments My thoughts exactly, at first glance it appears to be simple, but it is far from Easy

apghr + 9 comments works like a charm

#include <bits/stdc++.h> using namespace std; #define L (s.size() + t.size()) int main(){ string s, t; int k, i; cin >> s >> t >> k; for(i = 0; s[i] == t[i]; i++); cout << (L <= k + i*2 && L%2 == k%2 || L < k ? "Yes" : "No"); return 0; }

(edit: cleared out some redundant code)

chandu_iitm2029 + 1 comment <= k at the end

apghr + 1 comment Not needed. When s.size() + t.size() == k, the previous part of the condition is always true.

shrads01 + 2 comments Can you explain me the need of diff%2 == k%2 ?

dekoder + 0 comments it checks whether both are even or both are odd ! because if that happens to be true then (k - diff) will always be even and string can always be build. HOW ?

by appending then deleting or vice-versa.

jadhavsaurabh191 + 0 comments check exact number of alphabates

lohit_cool + 1 comment can you please explain diff%2==k%2 condition?

Majka + 0 comments qwerasdf qwerzxcv 10 operations

substring qwer is the same in both strings, so diff = asdf+zxcv = 8, you need atleast 8 operations to create the required string(delete asdf and append zxcv).But then if they gave you exactly two more operations to work with (10), you could remove 'r' from qwer and then append it. If they gave you 12 you could do the same thing to 'e' . . .

ZeroBlankZero + 0 comments pretty decent . good job :)

mr_360 + 0 comments can u explain your logic?

mahima_goyen2015 + 0 comments can you please eplain the logic?

wohlwendk + 0 comments I'm a little late to the party, but this is undefined behaviour if s == t. Since you don't check whether i <= s.length(), s[i] might be out of bounds, and from there anything could happen. You got lucky here and there's no problems on the judge, but it might not always works

sravanthi100 + 1 comment can anyone explain the logic

wohlwendk + 2 comments Sure.

First, we try to find the minimum number of operations needed. For this, we check how large the largest common prefix of the two strings is; eg. if we have "hello" and "hellno", our largest common prefix is "hell". We compute the length of this prefix by

`for(i = 0; s[i] == t[i]; i++);`

.If we didn't have such a prefix, we'd have to first delete

`s.size()`

characters, then append`t.size()`

characters (`s.size() + t.size() = L`

steps in total). However, since we have a prefix of length`i`

, we can skip`i`

deletions and`i`

additions. Therefore, we need at least`L - 2*i`

operations in total. If`k`

is smaller than that, we can return early.`L <= k + i*2`

checks this.Now, if

`(k - (L - 2 * i)) % 2 == 0`

(which is equivalent to`k%2 == L%2`

), we can first do`L - 2*i`

operations to get the string`t`

, and then just append a character and immediately remove it. Since`(k - (L - 2 * i)) % 2 == 0`

means that the difference between`k`

and`L - 2*i`

is even, this is always possible.There is one more special case; since

`remove("") == ""`

, if we have`k >= L`

, we can just do`s.size()`

deletions, then another`k - L`

deletions, and`t.size()`

additions. In this special case, we can always find a way to convert`s`

to`t`

using`k`

operations.sravanthi100 + 0 comments thank you!

phychessics + 0 comments Thanks for this explicit explanation.

deepjashan2001 + 0 comments how you can think like that???

skur42 + 7 comments Don't just copy it figure out the logic

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); String t = in.next(); int k = in.nextInt(); int i; int check=0; for(i=0;i<s.length()&&i<t.length();i++) { if(s.charAt(i)!=t.charAt(i)) { break; } } int d=s.length()-i; int a=t.length()-i; int p=k-d-a; if(p==0) { System.out.println("Yes"); } else if(p<0) { System.out.println("No"); } else { if(p%2==0) { System.out.println("Yes"); } else { if(p>=(2*i)) {System.out.println("Yes");} else {System.out.println("No");} } } } }

kangkanlahkar1 + 2 comments I didnt get

if(p>=(2*i))

iitbRaj + 1 comment Assuming you understood everything above that part, u must have realised that if the difference p is odd, two cases arise...and in that non-trivial case when the string becomes empty(like in the example "aba")during the process when u delete extra elements so that the no. of operations reaches k,realise that the string should become empty in less than or equal to p/2 operations(the other delete operations will be "just like that")(i at this point of time is denoting the no. of characters left in the string is).so u can also write --- if(p/2>=i)....

sonali007 + 0 comments thnxx...it was great help.

smartgeek2110 + 0 comments this part is not yet clear

coolchand5725 + 0 comments [deleted]stabgan + 0 comments For the first time I enjoyed a Java code

Basu_97 + 0 comments Awesome solution!! I was trying to understand how many cases i have to consider. But your code just blew my mind. Really easy to understand. Quite a good one

lemanisar23 + 0 comments it is great solving. thanks!!!!

weudbewiud + 7 comments Quite a compact solution in Python.

Basically, I remove characters from the end of s until t starts with s and the number of missing characters to get to t is the number of operations left. I also break if there are no more operations or if s became empty. Afterwards I simply check whether I have enough operations left to add character to s to reach t.

#!/bin/python import sys s = raw_input().strip() t = raw_input().strip() k = int(raw_input().strip()) for ops_left in reversed(range(1, k + 1)): if s == t[:len(s)] and len(t) - len(s) == ops_left or len(s) == 0: break s = s[:-1] print "Yes" if len(t) - len(s) <= ops_left else "No"

msambitkumar1991 + 0 comments @tschmorleiz can you please explain the condition of the if statement?

iamkris + 0 comments Amazing!!

pramos + 3 comments Really nice solution!

I'm not sure why you're doing:

reversed(range(1, k+1))

when you could directly do:

range(k, 1, -1)

vedikagupta + 0 comments kindly explain!!

dabangayush369 + 0 comments it will be:

range (k, 0, -1) instead of range(k, 1, -1)

chandan37shaw + 0 comments though this is a genuine solution but not passing all test cases

kushchoudhary8 + 0 comments no of moves left should be exactly equal to k not less then!

Shikhar47 + 0 comments The solution is elegant but the complexity of the algorithm will be "n-squared" as the list slicing operation is O(n) inside a for loop

qayum_khan_usa + 1 comment Here is a less elegant solution in

**Python3**with the inputs handled in modern HackerRank. Originally, I had a`for`

instead of a`while`

loop, but a final`i=m-1`

could arise in two ways. Continuing`Shikhar47`

's remark on efficiency, my code is at worst`O(n)`

in time complexity.def appendAndDelete(s, t, k): if k >= len(s) + len(t) : return "Yes" i = 0 ; m = min( len(s), len(t) ) while i < m and s[i] == t[i] : i += 1 d = len(s)-i + len(t)-i if k < d : return "No" if k == d : return "Yes" return "No" if (k-d)%2 else "Yes"

singh_anjalii535 + 0 comments can you explain this statement... return "No" if (k-d)%2 else "Yes"

Sort 717 Discussions, By:

Please Login in order to post a comment