# Append and Delete

# Append and Delete

+ 66 comments Let me do my best to explain the different cases that could happen:

int commonLength = 0; for (int i=0; i<java.lang.Math.min(s.length(),t.length());i++){ if (s.charAt(i)==t.charAt(i)) commonLength++; else break; } //CASE A if((s.length()+t.length()-2*commonLength)>k){ System.out.println("No"); } //CASE B else if((s.length()+t.length()-2*commonLength)%2==k%2){ System.out.println("Yes"); } //CASE C else if((s.length()+t.length()-k)<0){ System.out.println("Yes"); } //CASE D else{ System.out.println("No"); }

CASE A:

What this case is finding is if k is bigger than the difference in length of the two strings.

example: s = "123456789", t = "1", k = 5

in this case, you definitely need a bigger k to transform s to t or vice versa, therefore you reject any such cases.

Case B:

now that the case has passed A, we can say that the total number of letters required to change is less than or equal to k.

however the next problem comes because the question specified that exactly k moves must be done, no more no less. this leads to an example whereby:

s = "010101", t = "01010", k = any EVEN number

OR

s = "010101", t = "010101", k = any ODD number

from these two examples you can see that only if k is odd/even matches the odd/even of number of different digits will such cases pass.

Case C:

However there is a way to overcome this odd/even problem if you are able to completely delete away one string as a deletion action on an empty string results in another empty string.

Example: s = '1' t = '101' k = 5

in this case, to get a S from T you could do delete-delete-delete-delete-add(1) and you will satisfy the condition.

Case D:

all other cases will fail the test

Hope i helped

+ 3 comments It should not be considered as an easy problem. I hardly solved it.

+ 11 comments works like a charm

#include <bits/stdc++.h> using namespace std; #define L (s.size() + t.size()) int main(){ string s, t; int k, i; cin >> s >> t >> k; for(i = 0; s[i] == t[i]; i++); cout << (L <= k + i*2 && L%2 == k%2 || L < k ? "Yes" : "No"); return 0; }

(edit: cleared out some redundant code)

+ 6 comments ### Java solution - passes 100% of test cases

From my HackerRank solutions.

**Case 1:**See if we can completely erase String*s*and append String*t*. If we need to waste operations to reach*k*operations, we can do so when String*s*has no characters.**Case 2:**See if we can convert String*s*to String*t*without completely erasing String*s*. We keep erasing charcters from String*s*until it becomes a prefix of String*t*. We then add the characters needed to turn String*s*into String*t*. If we need to waste operations to reach*k*operations, we can only do so in groups of 2 by doing an append and a delete.import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String s = scan.next(); String t = scan.next(); int k = scan.nextInt(); scan.close(); System.out.println(canConvert(s, t, k) ? "Yes" : "No"); } private static boolean canConvert(String s, String t, int k) { /* Case 1 */ if (s.length() + t.length() <= k) { return true; } /* Case 2 */ int i = 0; // represents index of 1st non-matching character for ( ; i < s.length() && i < t.length(); i++) { if (s.charAt(i) != t.charAt(i)) { break; } } int minOperations = (s.length() - i) + (t.length() - i); return k >= minOperations && (k - minOperations) % 2 == 0; } }

Let me know if you have any questions.

+ 10 comments Quite a compact solution in Python.

Basically, I remove characters from the end of s until t starts with s and the number of missing characters to get to t is the number of operations left. I also break if there are no more operations or if s became empty. Afterwards I simply check whether I have enough operations left to add character to s to reach t.

#!/bin/python import sys s = raw_input().strip() t = raw_input().strip() k = int(raw_input().strip()) for ops_left in reversed(range(1, k + 1)): if s == t[:len(s)] and len(t) - len(s) == ops_left or len(s) == 0: break s = s[:-1] print "Yes" if len(t) - len(s) <= ops_left else "No"

Sort 1093 Discussions, By:

Please Login in order to post a comment