In this post, we will solve Append and Delete HackerRank Solution. This problem (Append and Delete) is a part of HackerRank Algorithms series.
Task
You have two strings of lowercase English letters. You can perform two types of operations on the first string:
- Append a lowercase English letter to the end of the string.
- Delete the last character of the string. Performing this operation on an empty string results 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
.
Example. s = [a, b, c]
t = [d, e, f]
k = 6
To convert s to t, we first delete all of the characters in 3 moves. Next we add each of the characters of t in order. On the 6th move, you will have the matching string. Return Yes
.
If there were more moves available, they could have been eliminated by performing multiple deletions on an empty string. If there were fewer than 6 moves, we would not have succeeded in creating the new string.
Function Description
Complete the appendAndDelete function in the editor below. It should return a string, either Yes
or No
.
appendAndDelete has the following parameter(s):
- string s: the initial string
- string t: the desired string
- int k: the exact number of operations that must be performed
Returns
- string: either
Yes
orNo
Input Format
The first line contains a string s, the initial string.
The second line contains a string t, the desired final string.
The third line contains an integer k, the number of operations.
Constraints
- 1 <= |s| <= 100
- 1 <= |t| <= 100
- 1 <= k <= 100
- s and t consist of lowercase English letters, ascii[a – z].
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 return 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 return Yes
.
Sample Input 2
ashley
ash
2
Sample Output 2
No
Explanation 2
To convert ashley
to ash
a minimum of 3 steps are needed. Hence we print No
as answer.
Solution – Append and Delete – HackerRank Solution
C++
#include <iostream> #include <vector> #include <string> #include <string.h> #include <cmath> using namespace std; int main() { string s, t; cin >> s >> t; int k; cin >> k; int i = 0, j = 0; for (; i < (int)s.size() && j < (int)t.size(); ++i,++j) { if (s[i] != t[j]) break; } int need = ((int)s.size() - i) + ((int)t.size() - j); if ((need <= k && (k-need) % 2 == 0) || k >= (int)s.size() + (int)t.size()) { cout << "Yes"; } else { cout << "No"; } return 0; }
Python
#!/bin/python3 import sys def appendAndDelete(s, t, k): start = 0 ind = 0 to_del = 0 to_app = 0 while ind < len(s) and ind < len(t) and s[ind] == t[ind]: ind += 1 start = ind if start < len(s): to_del = len(s[start:]) if to_del == len(s) and k - to_del >= len(t): return 'Yes' if start < len(t): to_app = len(t[start:]) k -= to_del + to_app #print("start = {} to_del = {} to_app = {} k = {}".format(start, to_del, to_app, k)) if k == 0 or (k > 0 and k % 2 == 0) or k >= 2*len(t): return 'Yes' else: return 'No' if __name__ == "__main__": s = input().strip() t = input().strip() k = int(input().strip()) result = appendAndDelete(s, t, k) print(result)
Java
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); String t = in.next(); int k = in.nextInt(); int toDelete = 0; int i = 0; while (i < s.length() && i < t.length() && s.charAt(i) == t.charAt(i)) { i++; } toDelete = s.length() - i; int ops = toDelete + (t.length() - i); if (ops <= k && ((k - ops) % 2 == 0 || (k - ops) > 2 * i)) { System.out.println("Yes"); } else { System.out.println("No"); } } }
Note: This problem (Append and Delete) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.