2977. Minimum Cost to Convert String II

/**
 * Problem: LeetCode 2977 - Minimum Cost to Convert String II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {
        int n = source.length();
        Map<String, Integer> strToId = new HashMap<>();
        int idCounter = 0;

        // Assign integer IDs to unique strings
        for (int i = 0; i < original.length; i++) {
            if (!strToId.containsKey(original[i])) {
                strToId.put(original[i], idCounter++);
            }
            if (!strToId.containsKey(changed[i])) {
                strToId.put(changed[i], idCounter++);
            }
        }

        int V = idCounter;
        final long INF = 1_000_000_000_000_000L; // 10^15 safely avoids overflow
        long[][] dist = new long[V][V];
        for (int i = 0; i < V; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        // Initialize direct transition costs (taking min for duplicate rules)
        for (int i = 0; i < original.length; i++) {
            int u = strToId.get(original[i]);
            int v = strToId.get(changed[i]);
            dist[u][v] = Math.min(dist[u][v], (long) cost[i]);
        }

        // Floyd-Warshall algorithm to find all-pairs shortest paths among substrings
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                if (dist[i][k] >= INF) continue;
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Collect distinct substring lengths for fast DP transitions
        Set<Integer> distinctLengthsSet = new TreeSet<>();
        for (String s : original) {
            distinctLengthsSet.add(s.length());
        }
        List<Integer> lengths = new ArrayList<>(distinctLengthsSet);

        // dp[i] = minimum cost to convert source[0..i-1] to target[0..i-1]
        long[] dp = new long[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            // Case 1: single character match (0 cost)
            if (source.charAt(i - 1) == target.charAt(i - 1) && dp[i - 1] < INF) {
                dp[i] = Math.min(dp[i], dp[i - 1]);
            }

            // Case 2: replace a valid substring of length L
            for (int L : lengths) {
                int j = i - L;
                if (j < 0) continue;
                if (dp[j] >= INF) continue;

                String subS = source.substring(j, i);
                String subT = target.substring(j, i);

                Integer u = strToId.get(subS);
                Integer v = strToId.get(subT);

                if (u != null && v != null && dist[u][v] < INF) {
                    dp[i] = Math.min(dp[i], dp[j] + dist[u][v]);
                }
            }
        }

        return dp[n] >= INF ? -1 : dp[n];
    }
}

"""
Problem: LeetCode 2977 - Minimum Cost to Convert String II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        n = len(source)
        str_to_id = {}
        id_counter = 0

        for orig, chg in zip(original, changed):
            if orig not in str_to_id:
                str_to_id[orig] = id_counter
                id_counter += 1
            if chg not in str_to_id:
                str_to_id[chg] = id_counter
                id_counter += 1

        V = id_counter
        INF = float('inf')
        dist = [[INF] * V for _ in range(V)]
        for i in range(V):
            dist[i][i] = 0

        for orig, chg, c in zip(original, changed, cost):
            u = str_to_id[orig]
            v = str_to_id[chg]
            if c < dist[u][v]:
                dist[u][v] = c

        # Floyd-Warshall with sparsity pruning
        for k in range(V):
            for i in range(V):
                if dist[i][k] == INF:
                    continue
                d_ik = dist[i][k]
                for j in range(V):
                    if d_ik + dist[k][j] < dist[i][j]:
                        dist[i][j] = d_ik + dist[k][j]

        distinct_lengths = sorted(list({len(s) for s in original}))

        dp = [INF] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):
            if source[i - 1] == target[i - 1] and dp[i - 1] < INF:
                dp[i] = min(dp[i], dp[i - 1])

            for L in distinct_lengths:
                j = i - L
                if j < 0:
                    continue
                if dp[j] == INF:
                    continue

                sub_s = source[j:i]
                sub_t = target[j:i]

                if sub_s in str_to_id and sub_t in str_to_id:
                    u = str_to_id[sub_s]
                    v = str_to_id[sub_t]
                    if dist[u][v] < INF:
                        dp[i] = min(dp[i], dp[j] + dist[u][v])

        return -1 if dp[n] == INF else dp[n]

/**
 * Problem: LeetCode 2977 - Minimum Cost to Convert String II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        int n = source.length();
        unordered_map<string, int> strToId;
        int idCounter = 0;

        for (size_t i = 0; i < original.size(); ++i) {
            if (strToId.find(original[i]) == strToId.end()) {
                strToId[original[i]] = idCounter++;
            }
            if (strToId.find(changed[i]) == strToId.end()) {
                strToId[changed[i]] = idCounter++;
            }
        }

        int V = idCounter;
        const long long INF = 1e16;
        vector<vector<long long>> dist(V, vector<long long>(V, INF));
        for (int i = 0; i < V; ++i) {
            dist[i][i] = 0;
        }

        for (size_t i = 0; i < original.size(); ++i) {
            int u = strToId[original[i]];
            int v = strToId[changed[i]];
            dist[u][v] = min(dist[u][v], (long long)cost[i]);
        }

        // Floyd-Warshall
        for (int k = 0; k < V; ++k) {
            for (int i = 0; i < V; ++i) {
                if (dist[i][k] >= INF) continue;
                for (int j = 0; j < V; ++j) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        set<int> lengthSet;
        for (const string& s : original) {
            lengthSet.insert(s.length());
        }

        vector<long long> dp(n + 1, INF);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            if (source[i - 1] == target[i - 1] && dp[i - 1] < INF) {
                dp[i] = min(dp[i], dp[i - 1]);
            }

            for (int L : lengthSet) {
                int j = i - L;
                if (j < 0) continue;
                if (dp[j] >= INF) continue;

                string subS = source.substr(j, L);
                string subT = target.substr(j, L);

                auto itS = strToId.find(subS);
                auto itT = strToId.find(subT);

                if (itS != strToId.end() && itT != strToId.end()) {
                    int u = itS->second;
                    int v = itT->second;
                    if (dist[u][v] < INF) {
                        dp[i] = min(dp[i], dp[j] + dist[u][v]);
                    }
                }
            }
        }

        return dp[n] >= INF ? -1 : dp[n];
    }
};

/**
 * Problem: LeetCode 2977 - Minimum Cost to Convert String II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} source
 * @param {string} target
 * @param {string[]} original
 * @param {string[]} changed
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(source, target, original, changed, cost) {
    const n = source.length;
    const strToId = new Map();
    let idCounter = 0;

    function getId(s) {
        if (!strToId.has(s)) {
            strToId.set(s, idCounter++);
        }
        return strToId.get(s);
    }

    const m = original.length;
    for (let i = 0; i < m; i++) {
        getId(original[i]);
        getId(changed[i]);
    }

    const V = idCounter;
    const INF = 1e16;
    const dist = Array.from({ length: V }, () => Array(V).fill(INF));
    for (let i = 0; i < V; i++) {
        dist[i][i] = 0;
    }

    for (let i = 0; i < m; i++) {
        const u = getId(original[i]);
        const v = getId(changed[i]);
        dist[u][v] = Math.min(dist[u][v], cost[i]);
    }

    // Floyd-Warshall
    for (let k = 0; k < V; k++) {
        for (let i = 0; i < V; i++) {
            if (dist[i][k] >= INF) continue;
            for (let j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    const lengths = Array.from(new Set(original.map(s => s.length)));

    const dp = Array(n + 1).fill(INF);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        if (source[i - 1] === target[i - 1] && dp[i - 1] < INF) {
            dp[i] = Math.min(dp[i], dp[i - 1]);
        }
        for (const L of lengths) {
            const j = i - L;
            if (j >= 0 && dp[j] < INF) {
                const subS = source.substring(j, i);
                const subT = target.substring(j, i);
                const u = strToId.get(subS);
                const v = strToId.get(subT);
                if (u !== undefined && v !== undefined && dist[u][v] < INF) {
                    dp[i] = Math.min(dp[i], dp[j] + dist[u][v]);
                }
            }
        }
    }

    return dp[n] >= INF ? -1 : dp[n];
};