Round 1
Questions: You are given two strings: X and Y, and two integers A and B. Your task is to form the string X using substrings from Y, and the cost of each substring depends on whether you take it from Y or its reverse. The cost of taking substrings from Y or reverse(Y) is different:
- Substrings of Y cost A per substring.
- Substrings of reverse(Y) cost B per substring.
You need to determine the minimum cost to form the string X using substrings from Y or its reverse. If it is impossible to form X using any combination of substrings from Y or reverse(Y), return -1.
Input:
- A string X of length m.
- A string Y of length n.
- Two integers A and B, where:
- A is the cost per substring taken from Y.
- B is the cost per substring taken from reverse(Y).
Output: Return the minimum cost to form the string X using substrings from Y and reverse(Y). If it is impossible to form X, return -1.
Example 1:
Input: X = "abc", Y = "aabbcc", A = 3, B = 5 Output: 6
Explanation: You can form "abc" by taking the substring ab from Y (cost = A = 3) and c from Y (cost = A = 3). Thus, the total cost is 3 + 3 = 6.
Example 2:
Input: X = "xyz", Y = "zyx", A = 2, B = 4 Output: 4
Explanation: You can form "xyz" by taking the entire reverse(Y) ("zyx") as a substring. The cost is B = 4.
Example 3:
Input: X = "abc", Y = "xyz", A = 3, B = 5 Output: -1
Explanation: It is impossible to form the string "abc" from Y or reverse(Y) because none of the characters in "abc" are present in Y or its reverse.
Constraints:
1 ≤ m, n ≤ 10000 (length of strings)
0 ≤ A, B ≤ 1000 (cost values)
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.