Quick Links

## Problem statement of Append and Delete

You are give two strings ** s** and

*as input. Objective is to convert*

**t***into*

**s***by using following two operations only:*

**t**1.

*a lowercase English alphabetic letter to the end of the string.*

**Append**2.

*the last character in the string. Performing this operation on an empty string results in an empty string.*

**Delete**You have to convert

**into**

*s***by performing exactly**

*t**number of operations. The original statement of Append and Delete challenge is available at Hackerrank.*

**K**## Observations and Solution

Total number of operations must be exactly ** K**. Lets discuss various possibilities and ways to determine them.

### Case K == |s|+|t|

If ** K** is equal to or greater than sum of lengths of

*and*

**s***. For instance*

**t**** s** = “askme”

**= 5**

*|s|*** t** = “askatul”

**= 7**

*|t|*Suppose ** K = 12** ( equal to

*). Here we can delete each element of*

**|s| + |t|****which requires**

*s**delete operations. Then in empty*

**5****we will append each character of**

*s**(*

**t****and**

*‘a’, ’s’, ’k’, ’a’, ’t’, ’u’**), which requires*

**’l’****append operations. So total number of operations done is**

*7***(**

*12**). So in this case if*

**= K****is**

*K**then answer is*

**12***.*

**YES**### Case K > |s|+|t|

Suppose ** K = 15 **(greater than

**). As per above discussion, here we have**

*|s|+|t|**extra operations. So we will first consume*

**3****operations in deleting each character of**

*5***. Now**

*s***is empty so now we will perform**

*s***more delete operations on empty string. As per the description of Delete operation**

*3***will remain empty. Then in empty**

*s***we will append each character of**

*s***(**

*t**and*

**‘a’, ’s’, ’k’, ’a’, ’t’, ’u’***), which requires*

**’l’****append operations. So total number of operations done is**

*7***(**

*5+3+7 = 15***). So the answer is**

*= k**.*

**YES**`if ( K > = |s| + |t|) then print : “YES” ;`

### Case K < |s| + |t|

Now we can not use logic discussed in previous two cases. So now we will calculate minimum number of steps, say** m**, required to convert

**to**

*s***.**

*t*#### Calculating minimum number of steps m to convert *s* into *t* –

*s*

*t*

First, find out longest common prefix * p* of

*and*

**s****. For above example**

*t**is*

**p***. Now minimum number of operations required to convert*

**“ask”****into**

*s**:*

**t***m = (|s| – |p|) + (|t| – |p|) = (|s| + |t|) – 2|p|*

For above example, ** m = 12 – 2*3 = 6**. Delete

*and*

**‘e’****from**

*‘m’**(*

**s****operations). Append**

*2***and**

*‘a’, ‘t’, ‘u’***in**

*‘l’***(**

*s***operations). So to convert**

*4***into**

*s**we need at least*

**t****operations. It is not possible to convert**

*6***to**

*“askme”***in less than**

*“askatul”***operations.**

*6*#### Case K < m

It’s a ** NO** case as discussed above.

#### Case K == m

It’s a **YES **case as discussed above.

#### Case K > m

In this case we have ** (K – m)** extra operations to be performed. In first

**operations we have converted**

*m***into**

*s***. Now extra**

*t***operations are to be performed on**

*(K-m)***(which is now equal to**

*s***) and the resultant string should remain equal to**

*t***.**

*t*Suppose ** “askme”** is converted into

*in first*

**“askatul”***operations. Now if we delete*

**6***, then the resultant string is*

**‘l’****and we have consumed**

*“askatu”***operation. Now we append**

*1**back in*

**‘l’***and the string becomes*

**“askatu”****.**

*“askatul”***more operation is consumed. So we consumed**

*1**operations and the string is retained as*

**2***. The conclusion of above discussion is if*

**“askatul”***then*

**K > m****extra operations can be consumed without changing resultant string if and only if**

*K – m***is even. If**

*(K – m)**is even then say*

**(K-m)***otherwise say*

**YES****.**

*NO*## Pseudo Code for Append and Delete

```
s is given as input.
t is given as input.
K is given as input.
if(K < n)
{
m = 0;
while(s[m] == t[m]) //calculating longest common prefix of s and t
.
m = m +1;
if(K == m)
Print : “YES” ;
else if (K>m && (K-m)%2 == 0)
Print : “YES”;
else
Print : “NO” ;
}
Else Print : “YES”;
```

Recommended Posts-

Organizing Containers of Balls

Circular Array Rotation

Insertion Sort Advanced Analysis

Can we ditch python for competitive coding?

5 C functions for competitive programming?

Prefix Sum : Query Time O(1) : Pre-processing Time O(n)