Transform String
Source: codechef
Difficulty: 1665

Transform String
Chef gives you 2 strings$A$and$B$. You can perform the following operation on$A$as many times as you want.
Remove character$A_{i}$from the string$A$. This has a cost of$i$which is the index of the element that you are removing.
Note that cost is always equal to the index in current string and not the original string.
Refer to the sample test case for example.
You have to print the minimum cost of transforming$A$to$B$using the above operation. If it is not possible to transform string$A$to$B$, print$-1$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of 2 lines of input.
The first line of each test case contains string$A$.
The next line contains string$B$.
Output Format
For each test case, output on a new line the minimum cost of transforming string$A$to$B$. If it is not possible to transform string$A$to string$B$using above operation, print$-1$.
Constraints$1 \leq T \leq 2 \cdot 10^5$$1 \leq |A| \leq 2 \cdot 10^5$($|A|$refers to length of string$A$)$1 \leq |B| \leq 2 \cdot 10^5$The sum of$|A|$and$|B|$over all test cases won't exceed$2 \cdot 10^5$.
Sample 1:
Explanation:
Test Case 1
:
Remove$A_{1}$which is the character
a
with cost of$1$,$A$becomes
ccd
.
Remove$A_1$which is the character
c
with cost of 1,$A$becomes
cd
which is equal to$B$.
Total cost is$2$.
Test Case 2
:
It is not possible to transform string$A$to$B$using the operation.
Test Case 3
:
Remove$A_{1}$with cost 1. Now,$A$is
aaabbb
.
Remove$A_{1}$with cost 1. Now,$A$is
aabbb
.
Remove$A_{3}$with cost 3. Now,$A$is
aabb
.
Remove$A_{3}$with cost 3. Now,$A$is
aab
.
Remove$A_{3}$with cost 3. Now,$A$is
aa
which is equal to$B$.
Total cost is$11$.

Sample Input:
3
accd
cd
abcd
ed
aaaabbb
aa

Sample Output:
2
-1
11

C++ solution:
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
template <typename T, typename Y>
istream &operator>>(istream &is, pair<T, Y> &p)
{
    is >> p.first >> p.second;
    return is;
}
template <typename T, typename Y>
ostream &operator<<(ostream &os, pair<T, Y> p)
{
    os << p.first << ' ' << p.second << ' ';
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &i : v)
        is >> i;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v)
{
    for (auto &i : v)
        os << i << ' ';
    return os;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin >> t;
    while (t--)
    {
        string s, t;
        cin >> s >> t;
        int j = t.size() - 1;
        int ans = 0;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            if (s[i] == t[j])
            {
                j--;
            }
            else
            {
                ans += (j + 2);
            }
        }
        if (j >= 0)
        {
            cout << -1 << endl;
        }
        else
        {
            cout << ans << endl;
        }
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "sort"
)

func main() {
    // Buffered I/O for efficiency.
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    
    // Read the number of test cases.
    line, _ := reader.ReadString('\n')
    t, _ := strconv.Atoi(strings.TrimSpace(line))
    
    // Process each test case.
    for tc := 0; tc < t; tc++ {
        // Read string A.
        A, _ := reader.ReadString('\n')
        A = strings.TrimSpace(A)
        // Read string B.
        B, _ := reader.ReadString('\n')
        B = strings.TrimSpace(B)
        
        n := len(A)
        m := len(B)
        
        // Precompute positions (1-indexed) for each character in A.
        // pos[0] corresponds to 'a', pos[1] to 'b', etc.
        pos := make([][]int, 26)
        for i := 0; i < n; i++ {
            ch := A[i] - 'a'
            pos[ch] = append(pos[ch], i+1)
        }
        
        // Now, we want to choose indices for B (from B[m-1] down to B[0])
        // such that the chosen index for B[i] is as far to the right as possible,
        // while ensuring the chosen index for B[i] is less than the chosen index for B[i+1].
        limit := n + 1 // The next chosen index must be strictly less than this value.
        var sumChosen int64 = 0
        possible := true
        
        // Iterate over B in reverse order.
        for i := m - 1; i >= 0; i-- {
            c := B[i] - 'a'
            arr := pos[c]
            // In arr (which is sorted in increasing order), we need the largest value less than 'limit'.
            // sort.Search finds the first index where arr[j] >= limit.
            idx := sort.Search(len(arr), func(j int) bool { return arr[j] >= limit })
            if idx == 0 {
                // No valid occurrence found.
                possible = false
                break
            }
            chosen := arr[idx-1]
            sumChosen += int64(chosen)
            limit = chosen // Update the limit for the next (previous in B) character.
        }
        
        if !possible {
            fmt.Fprintln(writer, -1)
            continue
        }
        
        // Now compute the cost.
        // cost = (m+1)*n - (m*(m+1))/2 - (sum of chosen indices)
        M := int64(m)
        N := int64(n)
        cost := (M+1)*N - (M*(M+1))/2 - sumChosen
        fmt.Fprintln(writer, cost)
    }
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), i, j;
            long count;
            StringBuilder a = new StringBuilder(), b = new StringBuilder();
  
            while(__ -- > 0) {
                next(a); next(b);
                i = a.length() - 1; j = b.length() - 1;
                count = 0;
                
                while(i >= 0 && j >= 0) {
                    if(a.charAt(i) == b.charAt(j)) {
                        j--;
                    } else count += j + 2;
                    
                    i--;
                }
                
                count += i + 1;
                
                outData.append(j < 0 ? count : -1).append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
function solve(str1, str2) {
    const n = str1.length;
    const m = str2.length;
    let v = [];
    
    let j = m - 1;
    for (let i = n - 1; i >= 0; i--) {
        if (j >= 0 && str1[i] === str2[j]) {
            v.push(i + 1);
            j--;
        }
    }
    
    if (j >= 0) {
        console.log(-1);
        return;
    }
    
    v.reverse();
    
    let s = 0;
    for (let it of v) {
        s += it;
    }
    
    let cnt = m * n + n - m - (m * (m - 1) / 2) - s;
    console.log(cnt);
}

let input = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
let t = parseInt(input[0]);

for (let i = 1; i <= t; i++) {
    let str1 = input[i * 2 - 1];
    let str2 = input[i * 2];
    solve(str1, str2);
}

Python solution:
# cook your dish here
import sys
import heapq
from collections import defaultdict
from bisect import bisect_left,bisect_right
from random import randint
class mydict:
    def __init__(self, func=lambda: 0):
        self.random = randint(0, 1 << 32)
        self.default = func
        self.dict = {}
    def __getitem__(self, key):
        mykey = self._get_hashed_key(key)
        if mykey not in self.dict:
            self.dict[mykey] = self.default()
        return self.dict[mykey]
    def get(self, key, default):
        mykey = self._get_hashed_key(key)
        if mykey not in self.dict:
            return default
        return self.dict[mykey]
    def __setitem__(self, key, item):
        mykey = self._get_hashed_key(key)
        self.dict[mykey] = item
    def _get_hashed_key(self, key):
        return self.random ^ hash(key)
    def getkeys(self):
        return [self.random ^ i for i in self.dict]
    def __str__(self):
        return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'
def input_list():
    return list(map(int, input().split()))
def input_str_list():
    return list(map(str, input().split()))
def input_numbers():
    return map(int, input().split())
def solve():
    a = input()
    b = input()
    if len(b)>len(a):
        return -1
    idxes = []
    j = len(b)-1
    for i in range(len(a)-1,-1,-1):
        if a[i] == b[j]:
            idxes.append(i)
            j-=1
            if j == -1:
                break
    ans = 0
    idxes = idxes[::-1]
    if len(idxes)!=len(b):
        return -1
    cur_idx = 1
    j = 0
    for i in range(len(a)):
        if j == len(idxes):
            ans+=cur_idx
            continue
        if i != idxes[j]:
            ans+=cur_idx
        else:
            cur_idx+=1
            j+=1
    return ans
            
t = int(input())
for _ in range(t):
    print(solve())

Ruby solution:
def solve
  t = gets.to_i
  t.times do
    a = gets.chomp
    b = gets.chomp
    
    n = a.size
    m = b.size
    
    i = n - 1
    j = m - 1
    ans = 0
    
    while i >= 0
      if j >= 0 && a[i] == b[j]
        j -= 1
      else
        ans += j + 2
      end
      i -= 1
    end
    
    if j >= 0
      puts -1
    else
      puts ans
    end
  end
end

solve