Problem of The Day 5 January — Append and Delete

Append and Delete

You have a string,s, of lowercase English alphabetic letters. You can perform two types of operations on s:

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 result in an empty string.

Given an integer, k, and two strings, s and t, 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.

Input Format

The first line contains a string, s, denoting the initial string.
The second line contains a string, t, denoting the desired final string. The third line contains an integer, k, denoting the desired number of operations.

Constraints

• 1 ≤ |s| ≤ 100
• 1 ≤ |t| ≤ 100
• 1 ≤ k ≤ 100
• s and t consist of lowercase English alphabetic letters.

Output Format

Print Yes if you can obtain string t by performing exactly k operations on s; otherwise, print No.

Sample Input 0

hackerhappy
hackerrank
9

Sample Output 0

Yes

Explanation 0

We perform 5 delete operations to reduce string s to hacker Next, we perform 4 append operations (i.e., r, a, n, and k), to get hackerrank. Because we were able to convert s to t by performing exactly k=9 operations, we print Yes.

Sample Input 1

aba
aba
7

Sample Output 1

Yes

Explanation 1

We perform 4 delete operations to reduce string s to the empty string (recall that, though the string will be empty after 3 deletions, we can still perform a delete operation on an empty string to get the empty string). Next, we perform 3 append operations (i.e., a, b, and a). Because we were able to convert s to t by performing exactly k=7 operations, we print Yes.

Problem Link: Append and Delete

Solution will be posted tomorrow.

SOLUTION

If we can obtain string by performing operations, then we can also obtain it in x+2.i operations for any i>=1 by repeatedly deleting and re‐appending the last character. Thus, it’s sufficient to find some minimal even and minimal odd v such that t can be obtained in operations.
We denote the length of the longest common prefix of s and t to be p. Because we know that the first p characters in s and t are the same in both strings, that tells us the minimum number of operations we must perform is d = |s| + |t| -2.p. If d is of the same parity as k, we can simply
check that k>=d.
If d and k do not have the same parity, the only way we can change the parity of the length of the string after k steps is to perform a deletion on an empty word. This means we must erase s, perform
an additional delete operation, and then append each character in t for a total of f=|s| + |t|+1 operations. Then we print Yes if and only if k>=f.

CODE

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
int main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
#endif
string s, t;
int k;
cin >> s >> t >> k;
int p = 0;
while (p < min(sz(s), sz(t)) && s[p] == t[p])
++p;
int vmin;
if (k % 2 == (sz(s) + sz(t)) % 2)
vmin = sz(s) + sz(t) ‐ 2 * p;
else
vmin = sz(s) + sz(t) + 1;
if (k < vmin)
cout << "No\n";
else
cout << "Yes\n"; 
} 
CODE courtesy hackkerrank editorial.