Append and Delete

See the original problem on HackerRank.

Solutions

The challenging part of this exercise is how to handle operations in excess.

If a string is empty, we can consume as many operations we want (as the problem specifies).

So, the easy case is when we have a number of operations that is greater than the sum of length of both strings. In this case the solution is “Yes” because we can just remove all the characters from one, consume excess operations by repeatedly performing the second operation from the empty string, and finally appending the other characters.

The other - more challenging - case is when we have longer strings. In this case, we can remove the last part not in common, then add the difference as long as the number of characters is less than or equal to the number of available operations.

However, we need to handle excess operations as well.

Consider the example:

1
2

hackerrank
hackerhappy

We have 9 operations.

We can remove rank or happy and add the rest accordingly. If we remove rank we consume 4 operations, then we add happy and consume 5 operations. Analogously, we do the opposite but the result is the same.

If we had 10 operations, the problem would have no valid solution because we have an extra operation to perform we cannot consume “in vain”. On the other hand, if we had 11 operations, we would consume such two extra operations by removing and re-adding the last character.

So we can express a very simple observation: if we can obtain a certain string by performing \(x\) operations then we can obtain it by performing \(x + 2 \cdot i\), that is by repeatedly deleting and re-appending the last character. This way, we handle “redundant” operations.

This observation helps solve the second case because we can use it as long as the parity of the number of operations (\(k\)) is the same as the total number of characters in the last part not in common between the two strings.

So, in the example above, we have 9 operations and the total number of characters in the last part not in common is 9. The parity is the same.

If we had 11, 13, etc operations, we would be on the safe side. If we had 12, 14, etc we would not be.

Here is a C++ solution:

1
2
3
4
5

string s1, s2; cin >> s1 >> s2;
int k; cin >> k;
auto mismIndex = distance(begin(s1), mismatch(begin(s1), end(s1), begin(s2)).first);
auto diff = s1.size() + s2.size() - mismIndex*2;
cout << ((diff <= k && diff%2 == k%2) || s1.size() + s2.size() < k ? "Yes" : "No");

std::mismatch is used to find the last part not in common.

The same approach in Haskell follows:

1
2
3
4
5
6
7
8

appendAndDelete s t k = canRemAddLast || canRemAll
  where
    commonLen = length $ takeWhile (uncurry (==)) (zip s t)
    sLen = length s
    tLen = length t
    diff = (sLen + tLen - (2 * commonLen))
    canRemAddLast = diff <= k && (even $ k - diff)
    canRemAll = sLen + tLen < k

Another approach, quite similar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

string s1, s2; cin >> s1 >> s2;
int k; cin >> k;
auto partInCommonSize = distance(begin(s1), mismatch(begin(s1), end(s1), begin(s2)).first);
int diff = s1.size() + s2.size() - partInCommonSize*2;
auto delta = k - diff;
if ((s1.size() + s2.size() < k) || (delta >= 0 && delta % 2 == 0))
    cout << "Yes";
else
{
    cout << "No";
}