12 days ago

Rohit • 40

Hyderabad

Minimum Cost String Transformation

Problem Statement:

Given two strings s and t, determine the minimum total cost required to transform s into t using the following operation any number of times, including zero:

• Select an index i such that 0 <= i <length of s.
• Remove the character at index i.
• Concatenate the remaining characters in order.
• The step costs i units.

If the transformation is not possible, return -1.

Constraints:

• 1 <= length of  s, t <= 2 *10^5
• Strings s and t contain only lowercase English letters.

13 hours ago

admin 1.9k

Sehore

Problem 1 Solution 

Minimum Cost String Transformation Solution

Topics Involved / Prerequisites

• Greedy Algorithms
• Two Pointers
• Mathematical Sequences (Arithmetic Progression)

Overview

To transform s into t, we must remove m = |s| - |t| characters. If t is not a subsequence of s, it is impossible.

The core of this problem lies in the mathematics of the removal costs. If we remove characters from left to right, each removal shifts the remaining characters to the left.

• The 1st removed character (at original index j_0) costs j_0.
• The 2nd removed character (at original index j_1) has shifted left by 1, costing j_1 - 1.
• The r-th removed character (0-indexed) costs j_r - r.

The total cost formula for removing m characters from left to right is:

Since (m*(m-1))/2 is a strict constant based on lengths, minimizing the total cost strictly means minimizing the sum of the removed indices (j_r).

Conversely, minimizing the removed indices is mathematically identical to maximizing the sum of the kept indices. To maximize the indices of the characters we keep to form t, we simply use a greedy two-pointer approach, matching t with the rightmost possible characters in s.

Approach

1. Right-to-Left Greedy Matching

We initialize two pointers at the ends of strings s and t. We iterate backward through s. Whenever s[ptr_s] == t[ptr_t], we record ptr_s as a kept index, add it to our sum_kept_indices, and move ptr_t backward.

2. Validation

If we finish scanning s and ptr_t has not reached below 0, it means we couldn't find all characters of t in order. We return -1.

3. Math Computation

Once we have sum_kept_indices, we can quickly find the sum of the removed indices. The sum of all indices in s is (n*(n-1))/2.

• Removed Sum = Total Sum - Kept Sum
• Final Minimum Cost= Removed Sum - m*(m-1)/2

Code Implementation

#include <iostream>
#include <string>

using namespace std;

long long minCostTransform(const string& s, const string& t) {
    long long n = s.length();
    long long k = t.length();
    if (k > n) return -1;
    long long sum_kept_indices = 0;
    int ptr_t = k - 1;
    for (int ptr_s = n - 1; ptr_s >= 0 && ptr_t >= 0; --ptr_s) {
        if (s[ptr_s] == t[ptr_t]) {
            sum_kept_indices += ptr_s;
            ptr_t--;
        }
    }
    if (ptr_t >= 0) return -1;

    long long m = n - k;
  
    long long total_s_indices = n * (n - 1) / 2;
    long long sum_removed_indices = total_s_indices - sum_kept_indices;
    long long min_cost = sum_removed_indices - (m * (m - 1) / 2);

    return min_cost;
}

Time and Space Complexity

• Time Complexity: O(N) — Where N is the length of string s. We traverse the string backwards exactly once.
• Space Complexity: O(1) — We only use a few 64-bit integer variables to store our sums and pointers.