Append and Delete - hackerrank

In [1]:

import sys
sys.path.append("/home/swyoo/algorithm/")

Append and Delete

hackerrank

Key Idea

Note that the algorithm should delete all characters until reacing LCS(Longest Common Prefix).
And then, append some characters to make the target string. There are some exceptions.

1. k operation is large enough to make target string.
2. residual operations can be used append and delete until making target string.
   • Note that the number of residual operations should be even.

In [4]:

def solve(s, t, k):
    if len(s) + len(t) <= k: return "Yes" # exception.
    i, r = 0, min(len(s), len(t))
    while i < r and s[i] == t[i]: i += 1
    even = len(t) - len(s) + k
    n = len(s) - i + len(t) - i # of total operations.
    if k < n: return "No"
    if k == n: return "Yes"
    return "No" if (k-n)%2 else "Yes" # if residual operations remain.

In [5]:

s = "hackerhappy"
t = "hackerrank"
k = 9

In [6]:

solve(s, t, k)

'Yes'

Time Complexity

$O(n)$

Report

easy 문제였지만, enumerate하는 과정에서 exception들을 잘 고려야했다. exception들을 잘 처리하는 것도 중요한 문제이다.