Append and Delete

Problem statement of Append and Delete

You are give two strings s and t as input. Objective is to convert s into t by using following two operations only:
1. Append a lowercase English alphabetic letter to the end of the string.
2. Delete the last character in the string. Performing this operation on an empty string results in an empty string.
You have to convert s into t by performing exactly K number of operations. The original statement of Append and Delete challenge is available at Hackerrank.

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 s and t. For instance

s = “askme”  
|s| = 5

t = “askatul”  
|t| = 7

Suppose K = 12 ( equal to |s| + |t|). Here we can delete each element of s which requires 5 delete operations. Then in empty s we will append each character of t (‘a’, ’s’, ’k’, ’a’, ’t’, ’u’ and ’l’), which requires 7 append operations. So total number of operations done is 12 (= K). So in this case if K is 12 then answer is YES.

Case K > |s|+|t|

Suppose K = 15 (greater than |s|+|t|). As per above discussion, here we have 3 extra operations. So we will first consume 5 operations in deleting each character of s. Now s is empty so now we will perform 3 more delete operations on empty string. As per the description of Delete operation s will remain empty. Then in empty s we will append each character of t (‘a’, ’s’, ’k’, ’a’, ’t’, ’u’ and ’l’), which requires 7 append operations. So total number of operations done is 5+3+7 = 15 (= k). So the answer is 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 s to t.

Calculating minimum number of steps m to convert s into t

First, find out longest common prefix p of s and t. For above example p is “ask”. Now minimum number of operations required to convert s into t :

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

For above example, m = 12 – 2*3 = 6. Delete ‘e’ and ‘m’ from s (2 operations). Append ‘a’, ‘t’, ‘u’ and ‘l’ in s (4 operations). So to convert s into t we need at least 6 operations. It is not possible to convert “askme” to “askatul” in less than 6 operations.

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 m operations we have converted s into t. Now extra (K-m) operations are to be performed on s (which is now equal to t) and the resultant string should remain equal to t.

Suppose “askme” is converted into “askatul” in first 6 operations. Now if we delete ‘l’, then the resultant string is “askatu” and we have consumed 1 operation. Now we append ‘l’ back in “askatu” and the string becomes “askatul”. 1 more operation is consumed. So we consumed 2 operations and the string is retained as “askatul”. The conclusion of above discussion is if K > m 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 YES otherwise say 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)

Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *