Minimize operations to make string Z equal to T by appending subsequence of S - Coding

Given two strings S and T, and an empty string Z, the task is to print the minimum operations required to make string Z equal to T by appending any subsequence of S at the end of Z. If it is impossible to do so, then print -1.

Example:

Input: S = “aabce”, T=”ace”
Output: 1

Input: S = “abacaba”, T = “aax”
Output: -1

Approach:

The idea is to precomputes the next occurrence (nextOccurrence) positions of each character in the source string S. Iterates backward through S and fills in this array with the rightmost positions of each character occurrence. Then, for each character in the target string T and traverses through the occurrences in S, updating the position and counting the operations needed. If the end of S is reached, resets the position to the beginning and increments the result. If a valid occurrence is not found for a character in T, the position is reset, and the result is incremented. If no valid occurrence is found while the position is at the beginning, the result is set to INF.

Steps:

Initialize a 2D array nextOccurrence to store the next occurrence position of each character in S.
Precompute the next occurrence positions for each character in S using the nextOccurrence array. This helps in efficiently finding the next occurrence of a character during the calculation.
Iterate through each character in the target string T.
- For each character, check if the next occurrence of that character in S is found using the nextOccurrence array.
- If found, update the position to the next occurrence position + 1.
- If not found, reset the position to the beginning of S and increment the result, indicating a new subsequence is appended.
- If it’s not possible to find the next occurrence, set result to INF, indicating impossibility.
Print the final result. If result is greater than or equal to INF, print -1, else print the number of operations needed.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_STR_SIZE = int(2e5) + 99;
const int INF = int(1e9) + 99;
 
string S, T;
int nextOccurrence[MAX_STR_SIZE][26];
 
// Function to calculate the minimum operations to make z
// equal to T
int calculateOperations()
{
    int result = 1, position = 0;
 
    // Iterate through the characters in the target string
    for (int i = 0; i < T.size(); ++i) {
        // Reset position to the beginning of the source
        // string if reached its end
        if (position == S.size()) {
            position = 0;
            ++result;
        }
 
        // If the next occurrence of the current character
        // in S is not found
        if (nextOccurrence[position][T[i] - 'a'] == INF) {
            // Reset position to the beginning and increment
            // the result
            position = 0;
            ++result;
        }
 
        // If the next occurrence is not found and the
        // position is at the beginning
        if (nextOccurrence[position][T[i] - 'a'] == INF
            && position == 0) {
            result = INF;
            break;
        }
 
        // Move the position to the next occurrence + 1
        position = nextOccurrence[position][T[i] - 'a'] + 1;
    }
 
    return result;
}
 
int main()
{
    S = "aabce", T = "ace";
 
    // Initialize nextOccurrence array with INF values
    for (int i = 0; i < S.size() + 5; ++i)
        for (int j = 0; j < 26; ++j)
            nextOccurrence[i][j] = INF;
 
    // Precompute the next occurrence positions for each
    // character in S
    for (int i = int(S.size()) - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j)
            nextOccurrence[i][j] = nextOccurrence[i + 1][j];
        nextOccurrence[i][S[i] - 'a'] = i;
    }
 
    // Calculate the minimum operations and print the result
    int result = calculateOperations();
    if (result >= INF)
        cout << -1 << endl;
    else
        cout << result << endl;
 
    return 0;
}

Java

public class MinOperations {
 
    static final int MAX_STR_SIZE = (int)(2e5) + 99;
    static final int INF = (int)(1e9) + 99;
    static String S, T;
    static int[][] nextOccurrence
        = new int[MAX_STR_SIZE][26];
 
    // Function to calculate the minimum operations to make
    // z equal to T
    static int calculateOperations()
    {
        int result = 1, position = 0;
 
        // Iterate through the characters in the target
        // string
        for (int i = 0; i < T.length(); ++i) {
            // Reset position to the beginning of the source
            // string if reached its end
            if (position == S.length()) {
                position = 0;
                ++result;
            }
 
            // If the next occurrence of the current
            // character in S is not found
            if (nextOccurrence[position][T.charAt(i) - 'a']
                == INF) {
                // Reset position to the beginning and
                // increment the result
                position = 0;
                ++result;
            }
 
            // If the next occurrence is not found and the
            // position is at the beginning
            if (nextOccurrence[position][T.charAt(i) - 'a']
                    == INF
                && position == 0) {
                result = INF;
                break;
            }
 
            // Move the position to the next occurrence + 1
            position = nextOccurrence[position]
                                     [T.charAt(i) - 'a']
                       + 1;
        }
 
        return result;
    }
 
    public static void main(String[] args)
    {
        S = "aabce";
        T = "ace";
 
        // Initialize nextOccurrence array with INF values
        for (int i = 0; i < S.length() + 5; ++i)
            for (int j = 0; j < 26; ++j)
                nextOccurrence[i][j] = INF;
 
        // Precompute the next occurrence positions for each
        // character in S
        for (int i = S.length() - 1; i >= 0; --i) {
            for (int j = 0; j < 26; ++j)
                nextOccurrence[i][j]
                    = nextOccurrence[i + 1][j];
            nextOccurrence[i][S.charAt(i) - 'a'] = i;
        }
 
        // Calculate the minimum operations and print the
        // result
        int result = calculateOperations();
        if (result >= INF)
            System.out.println(-1);
        else
            System.out.println(result);
    }
}

Python3

# Python program for the above approach
MAX_STR_SIZE = int(2e5) + 99
INF = int(1e9) + 99
 
S = "aabce"
T = "ace"
 
next_occurrence = [[INF] * 26 for _ in range(MAX_STR_SIZE)]
 
# Function to calculate the minimum operations to make z equal to T
def calculate_operations():
    result = 1
    position = 0
 
    # Iterate through the characters in the target string
    for i in range(len(T)):
        # Reset position to the beginning of the source string if reached its end
        if position == len(S):
            position = 0
            result += 1
 
        # If the next occurrence of the current character in S is not found
        if next_occurrence[position][ord(T[i]) - ord('a')] == INF:
            # Reset position to the beginning and increment the result
            position = 0
            result += 1
 
        # If the next occurrence is not found and the position is at the beginning
        if (
            next_occurrence[position][ord(T[i]) - ord('a')] == INF
            and position == 0
        ):
            result = INF
            break
 
        # Move the position to the next occurrence + 1
        position = next_occurrence[position][ord(T[i]) - ord('a')] + 1
 
    return result
 
# Initialize next_occurrence array with INF values
for i in range(len(S) + 5):
    for j in range(26):
        next_occurrence[i][j] = INF
 
# Precompute the next occurrence positions for each character in S
for i in range(len(S) - 1, -1, -1):
    for j in range(26):
        next_occurrence[i][j] = next_occurrence[i + 1][j]
    next_occurrence[i][ord(S[i]) - ord('a')] = i
 
# Calculate the minimum operations and print the result
result = calculate_operations()
if result >= INF:
    print(-1)
else:
    print(result)
 
# This code is contributed by Susobhan Akhuli

C#

// C# program for the above approach
using System;
 
public class GFG {
    const int MAX_STR_SIZE = (int)2e5 + 99;
    const int INF = (int)1e9 + 99;
 
    static string S, T;
    static int[, ] nextOccurrence
        = new int[MAX_STR_SIZE, 26];
 
    // Function to calculate the minimum operations to make
    // z equal to T
    static int CalculateOperations()
    {
        int result = 1, position = 0;
 
        // Iterate through the characters in the target
        // string
        for (int i = 0; i < T.Length; ++i) {
            // Reset position to the beginning of the source
            // string if reached its end
            if (position == S.Length) {
                position = 0;
                ++result;
            }
 
            // If the next occurrence of the current
            // character in S is not found
            if (nextOccurrence[position, T[i] - 'a']
                == INF) {
                // Reset position to the beginning and
                // increment the result
                position = 0;
                ++result;
            }
 
            // If the next occurrence is not found and the
            // position is at the beginning
            if (nextOccurrence[position, T[i] - 'a'] == INF
                && position == 0) {
                result = INF;
                break;
            }
 
            // Move the position to the next occurrence + 1
            position
                = nextOccurrence[position, T[i] - 'a'] + 1;
        }
 
        return result;
    }
 
    static void Main()
    {
        S = "aabce";
        T = "ace";
 
        // Initialize nextOccurrence array with INF values
        for (int i = 0; i < S.Length + 5; ++i)
            for (int j = 0; j < 26; ++j)
                nextOccurrence[i, j] = INF;
 
        // Precompute the next occurrence positions for each
        // character in S
        for (int i = S.Length - 1; i >= 0; --i) {
            for (int j = 0; j < 26; ++j)
                nextOccurrence[i, j]
                    = nextOccurrence[i + 1, j];
            nextOccurrence[i, S[i] - 'a'] = i;
        }
 
        // Calculate the minimum operations and print the
        // result
        int result = CalculateOperations();
        if (result >= INF)
            Console.WriteLine(-1);
        else
            Console.WriteLine(result);
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// Javascript program for the above approach
const MAX_STR_SIZE = 2e5 + 99;
const INF = 1e9 + 99;
 
let S, T;
let nextOccurrence = Array.from({ length: MAX_STR_SIZE }, () => Array(26).fill(INF));
 
// Function to calculate the minimum operations to make z equal to T
function calculateOperations() {
    let result = 1;
    let position = 0;
 
    // Iterate through the characters in the target string
    for (let i = 0; i < T.length; ++i) {
        // Reset position to the beginning of the source string if reached its end
        if (position === S.length) {
            position = 0;
            ++result;
        }
 
        // If the next occurrence of the current character in S is not found
        if (nextOccurrence[position][T.charCodeAt(i) - 'a'.charCodeAt(0)] === INF) {
            // Reset position to the beginning and increment the result
            position = 0;
            ++result;
        }
 
        // If the next occurrence is not found and the position is at the beginning
        if (nextOccurrence[position][T.charCodeAt(i) - 'a'.charCodeAt(0)] === INF && position === 0) {
            result = INF;
            break;
        }
 
        // Move the position to the next occurrence + 1
        position = nextOccurrence[position][T.charCodeAt(i) - 'a'.charCodeAt(0)] + 1;
    }
 
    return result;
}
 
// Main function
S = "aabce";
T = "ace";
 
// Initialize nextOccurrence array with INF values
for (let i = 0; i < S.length + 5; ++i) {
    for (let j = 0; j < 26; ++j) {
        nextOccurrence[i][j] = INF;
    }
}
 
// Precompute the next occurrence positions for each character in S
for (let i = S.length - 1; i >= 0; --i) {
    for (let j = 0; j < 26; ++j) {
        nextOccurrence[i][j] = nextOccurrence[i + 1][j];
    }
    nextOccurrence[i][S.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
 
// Calculate the minimum operations and print the result
let result = calculateOperations();
if (result >= INF)
    console.log(-1);
else
    console.log(result);
 
// This code is contributed by Susobhan Akhuli

Output

Time Complexity: O(n+m), where n is the size of string s and m is the size of string t.
Auxiliary Space: O(n)

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Find number of Strictly Increasing Sequences with 'a' and 'b' in a String
Dynamic Programming (DP) on Grids
Winning and Losing States for Competitive Programming
Maximizing Chocolates in Grid using 2 robots (Chocolates Pickup)
Find the LCS of string such that it does not contains the given string

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15