Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Append and delete challenge

Sharing is caring!

Problem statement
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 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.

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 \le |s| \le 100
1 \le |t| \le 100
1 \le k \le 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.

Solution

public class AppendAndDelete {

    private static String solve(String s, String t, int k) {
        // common prefix length
        int j = 0;
        for (int i = 0; i < Math.min(t.length(), s.length()); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                break;
            } else {
                j++;
            }
        }

        if ((s.length() + t.length() - 2 * j) > k) {
            // s = xxxabc
            // t = xxxhklmn
            // k = 2
            return "No";
        }

        if ((s.length() + t.length() - 2 * j) % 2 == k % 2) {
            // For every non-matching char in s, delete it and add a char from t (2 operations - delete, add).
            // Any remaining operations can be done at the beginning as delete operations for matching chars as well.
            return "Yes";
        }

        if (s.length() + t.length() < k) {
            // We have enough operations left to delete the entire string s and append t.length caharacters
            return "Yes";
        }

        return "No";

    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        String s = in.next();
        String t = in.next();
        int k = in.nextInt();

        System.out.println(solve(s, t, k));
    }
}