Given strings X and Y, and integers A and B, form the target string X by concatenating substrings taken from Y or its reverse. Each substring from Y costs A, and each from reverse(Y) costs B. Determine the minimum total cost to form X, or return -1 if it is impossible.
Input: X = "abc", Y = "aabbcc", A = 3, B = 5
Output: 6
Explanation: Form "abc" by taking substring "ab" from Y (cost A=3) and "c" from Y (cost A=3), total cost 6.
Input: X = "xyz", Y = "zyx", A = 2, B = 4
Output: 4
Explanation: Take entire reverse(Y) "zyx" as a substring with cost B=4.
Input: X = "abc", Y = "xyz", A = 3, B = 5
Output: -1
Explanation: Impossible since no characters in X are present in Y or its reverse.
The problem can be modeled as a shortest path problem where nodes are positions in the target string X, and edges represent taking a substring from Y or reverse(Y) with cost A or B, respectively. To efficiently determine valid edges, we use suffix automata for Y and reverse(Y) to compute, for each starting position in X, the maximum length of a substring that exists in Y or reverse(Y). This allows dynamic programming to find the minimum cost.
#include <bits/stdc++.h>
using namespace std;
struct State {
int len;
int link;
unordered_map<char, int> next;
};
class SuffixAutomaton {
vector<State> st;
int last;
public:
SuffixAutomaton(string s) {
st.push_back(State{0, -1, {}});
last = 0;
for (char c : s) {
extend(c);
}
}
void extend(char c) {
int cur = st.size();
st.push_back(State{st[last].len + 1, -1, {}});
int p = last;
while (p != -1 && st[p].next.find(c) == st[p].next.end()) {
st[p].next[c] = cur;
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].next[c];
if (st[q].len == st[p].len + 1) {
st[cur].link = q;
} else {
int clone = st.size();
st.push_back(State{st[p].len + 1, st[q].link, st[q].next});
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = clone;
st[cur].link = clone;
}
}
last = cur;
}
int longest_prefix(string s, int start) {
int state = 0;
int l = 0;
for (int i = start; i < s.size(); i++) {
char c = s[i];
if (st[state].next.find(c) != st[state].next.end()) {
state = st[state].next[c];
l++;
} else {
break;
}
}
return l;
}
};
int minimizeCost(string X, string Y, int A, int B) {
int n = X.size();
SuffixAutomaton autoY(Y);
SuffixAutomaton autoRevY(string(Y.rbegin(), Y.rend()));
vector<int> max_len_Y(n), max_len_revY(n);
for (int j = 0; j < n; j++) {
max_len_Y[j] = autoY.longest_prefix(X, j);
max_len_revY[j] = autoRevY.longest_prefix(X, j);
}
const long long INF = 1e18;
vector<long long> dp(n+1, INF);
dp[0] = 0;
for (int j = 0; j < n; j++) {
if (dp[j] == INF) continue;
int maxY = max_len_Y[j];
for (int i = j+1; i <= n && i <= j+maxY; i++) {
if (dp[i] > dp[j] + A) {
dp[i] = dp[j] + A;
}
}
int maxRev = max_len_revY[j];
for (int i = j+1; i <= n && i <= j+maxRev; i++) {
if (dp[i] > dp[j] + B) {
dp[i] = dp[j] + B;
}
}
}
return dp[n] == INF ? -1 : dp[n];
}
import java.util.*;
public class Solution {
static class State {
int len;
int link;
Map<Character, Integer> next;
State(int len, int link) {
this.len = len;
this.link = link;
this.next = new HashMap<>();
}
}
static class SuffixAutomaton {
List<State> st;
int last;
SuffixAutomaton(String s) {
st = new ArrayList<>();
st.add(new State(0, -1));
last = 0;
for (char c : s.toCharArray()) {
extend(c);
}
}
void extend(char c) {
int cur = st.size();
st.add(new State(st.get(last).len + 1, -1));
int p = last;
while (p != -1 && !st.get(p).next.containsKey(c)) {
st.get(p).next.put(c, cur);
p = st.get(p).link;
}
if (p == -1) {
st.get(cur).link = 0;
} else {
int q = st.get(p).next.get(c);
if (st.get(q).len == st.get(p).len + 1) {
st.get(cur).link = q;
} else {
int clone = st.size();
State cloneState = new State(st.get(p).len + 1, st.get(q).link);
cloneState.next.putAll(st.get(q).next);
st.add(cloneState);
while (p != -1 && st.get(p).next.get(c) == q) {
st.get(p).next.put(c, clone);
p = st.get(p).link;
}
st.get(q).link = clone;
st.get(cur).link = clone;
}
}
last = cur;
}
int longest_prefix(String s, int start) {
int state = 0;
int l = 0;
for (int i = start; i < s.length(); i++) {
char c = s.charAt(i);
if (st.get(state).next.containsKey(c)) {
state = st.get(state).next.get(c);
l++;
} else {
break;
}
}
return l;
}
}
public static int minimizeCost(String X, String Y, int A, int B) {
int n = X.length();
SuffixAutomaton autoY = new SuffixAutomaton(Y);
SuffixAutomaton autoRevY = new SuffixAutomaton(new StringBuilder(Y).reverse().toString());
int[] max_len_Y = new int[n];
int[] max_len_revY = new int[n];
for (int j = 0; j < n; j++) {
max_len_Y[j] = autoY.longest_prefix(X, j);
max_len_revY[j] = autoRevY.longest_prefix(X, j);
}
long INF = Long.MAX_VALUE / 2;
long[] dp = new long[n+1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int j = 0; j < n; j++) {
if (dp[j] == INF) continue;
int maxY = max_len_Y[j];
for (int i = j+1; i <= n && i <= j+maxY; i++) {
if (dp[i] > dp[j] + A) {
dp[i] = dp[j] + A;
}
}
int maxRev = max_len_revY[j];
for (int i = j+1; i <= n && i <= j+maxRev; i++) {
if (dp[i] > dp[j] + B) {
dp[i] = dp[j] + B;
}
}
}
return dp[n] == INF ? -1 : (int)dp[n];
}
}
class SuffixAutomaton:
def __init__(self, s):
self.states = [{'len':0, 'link':-1, 'next':{}}]
self.last = 0
for c in s:
self._extend(c)
def _extend(self, c):
cur = len(self.states)
self.states.append({'len': self.states[self.last]['len'] + 1, 'link': -1, 'next': {}})
p = self.last
while p != -1 and c not in self.states[p]['next']:
self.states[p]['next'][c] = cur
p = self.states[p]['link']
if p == -1:
self.states[cur]['link'] = 0
else:
q = self.states[p]['next'][c]
if self.states[q]['len'] == self.states[p]['len'] + 1:
self.states[cur]['link'] = q
else:
clone = len(self.states)
self.states.append({'len': self.states[p]['len'] + 1, 'link': self.states[q]['link'], 'next': self.states[q]['next'].copy()})
while p != -1 and self.states[p]['next'].get(c) == q:
self.states[p]['next'][c] = clone
p = self.states[p]['link']
self.states[q]['link'] = clone
self.states[cur]['link'] = clone
self.last = cur
def longest_prefix(self, s, start):
state = 0
l = 0
for i in range(start, len(s)):
c = s[i]
if c in self.states[state]['next']:
state = self.states[state]['next'][c]
l += 1
else:
break
return l
def minimize_cost(X, Y, A, B):
n = len(X)
autoY = SuffixAutomaton(Y)
autoRevY = SuffixAutomaton(Y[::-1])
max_len_Y = [0] * n
max_len_revY = [0] * n
for j in range(n):
max_len_Y[j] = autoY.longest_prefix(X, j)
max_len_revY[j] = autoRevY.longest_prefix(X, j)
INF = 10**18
dp = [INF] * (n+1)
dp[0] = 0
for j in range(n):
if dp[j] == INF:
continue
maxY = max_len_Y[j]
for i in range(j+1, min(n+1, j+maxY+1)):
if dp[i] > dp[j] + A:
dp[i] = dp[j] + A
maxRev = max_len_revY[j]
for i in range(j+1, min(n+1, j+maxRev+1)):
if dp[i] > dp[j] + B:
dp[i] = dp[j] + B
return dp[n] if dp[n] != INF else -1
if __name__ == "__main__":
X = "abc"
Y = "aabbcc"
A = 3
B = 5
print(minimize_cost(X, Y, A, B))
class SuffixAutomaton {
constructor(s) {
this.states = [{len:0, link:-1, next: new Map()}];
this.last = 0;
for (let c of s) {
this.extend(c);
}
}
extend(c) {
let cur = this.states.length;
this.states.push({len: this.states[this.last].len + 1, link: -1, next: new Map()});
let p = this.last;
while (p !== -1 && !this.states[p].next.has(c)) {
this.states[p].next.set(c, cur);
p = this.states[p].link;
}
if (p === -1) {
this.states[cur].link = 0;
} else {
let q = this.states[p].next.get(c);
if (this.states[q].len === this.states[p].len + 1) {
this.states[cur].link = q;
} else {
let clone = this.states.length;
let cloneState = {
len: this.states[p].len + 1,
link: this.states[q].link,
next: new Map(this.states[q].next)
};
this.states.push(cloneState);
while (p !== -1 && this.states[p].next.get(c) === q) {
this.states[p].next.set(c, clone);
p = this.states[p].link;
}
this.states[q].link = clone;
this.states[cur].link = clone;
}
}
this.last = cur;
}
longest_prefix(s, start) {
let state = 0;
let l = 0;
for (let i = start; i < s.length; i++) {
let c = s[i];
if (this.states[state].next.has(c)) {
state = this.states[state].next.get(c);
l++;
} else {
break;
}
}
return l;
}
}
function minimizeCost(X, Y, A, B) {
let n = X.length;
let autoY = new SuffixAutomaton(Y);
let autoRevY = new SuffixAutomaton([...Y].reverse().join(''));
let max_len_Y = new Array(n).fill(0);
let max_len_revY = new Array(n).fill(0);
for (let j = 0; j < n; j++) {
max_len_Y[j] = autoY.longest_prefix(X, j);
max_len_revY[j] = autoRevY.longest_prefix(X, j);
}
let INF = 10**18;
let dp = new Array(n+1).fill(INF);
dp[0] = 0;
for (let j = 0; j < n; j++) {
if (dp[j] === INF) continue;
let maxY = max_len_Y[j];
for (let i = j+1; i <= Math.min(n, j+maxY); i++) {
if (dp[i] > dp[j] + A) {
dp[i] = dp[j] + A;
}
}
let maxRev = max_len_revY[j];
for (let i = j+1; i <= Math.min(n, j+maxRev); i++) {
if (dp[i] > dp[j] + B) {
dp[i] = dp[j] + B;
}
}
}
return dp[n] === INF ? -1 : dp[n];
}
// Example
let X = "abc", Y = "aabbcc", A = 3, B = 5;
console.log(minimizeCost(X, Y, A, B)); // 6
Time Complexity: O(n * m), where n is the length of X and m is the length of Y, due to suffix automaton construction and traversal for each starting position in X.
Space Complexity: O(m + n), for storing the suffix automata and DP arrays.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.