Diferencia máxima de índice adyacente para una subsecuencia T presente en una string dada S

Dadas dos strings S y T de longitudes n y m respectivamente. Encuentre la diferencia de índice adyacente máxima para los índices donde la string T está presente en la string S como una subsecuencia.

• El costo se define como la diferencia entre los índices de la subsecuencia T
• El costo máximo de una secuencia se define como max(a _i+1 −a _i ) para 1 ≤ i < m .
• Se garantiza que existe al menos una subsecuencia como T en S.

Ejemplos:

Entrada: S = “abbbc”, T = “abc” 
Salida: 3
Explicación: Una de las subsecuencias es {1, 4, 5} que denota la secuencia “abc” igual que T, por lo que el costo máximo es 4 – 1 = 3 .

Entrada: S = “aaaa”, T = “aa” 
Salida: 4
Explicación: Una de las subsecuencias es {1, 5} y el costo máximo es 5 – 1 = 4.

Enfoque: Para alguna subsecuencia de la string S, sea ai _la posición del carácter T _i en la string S. Para i fija, podemos encontrar una subsecuencia que maximice a _i+1 −a _i .

Siga los pasos a continuación para resolver el problema:

1. Sean _i izquierda y _i derecha el valor mínimo y máximo posible de una _i entre todas las a válidas respectivamente. Ahora, es fácil ver que el valor máximo posible de a _i+1 − a _i es igual a right _i+1 − left _i .
2. Para calcular _{la i} izquierda solo necesitamos encontrar el primer elemento después de la _i−1 izquierda que es igual a T _i , _{la i} derecha se puede encontrar de la misma manera al iterar en la dirección inversa.
3. Entonces, después de encontrar la izquierda y la derecha, la respuesta es max(right _i+1 −left _i ) para 1 ≤ i < m.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// cost of a subsequence
int maxCost(string s, string t, int n, int m)
{
    // mxCost stores the maximum
    // cost of a subsequence
    int mxCost = 0;
 
    // left[i] and right[i] store
    // the minimum and maximum
    // value of ai among all
    // valid a's respectively
    int left[m], right[m];
 
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (j >= m)
            break;
 
        if (s[i] == t[j]) {
            left[j] = i;
            j++;
        }
    }
 
    j = m - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (j < 0)
            break;
 
        if (s[i] == t[j]) {
            right[j] = i;
            j--;
        }
    }
 
    for (int i = 0; i < m - 1; i++) {
        mxCost = max(mxCost,
                     right[i + 1] - left[i]);
    }
 
    return mxCost;
}
 
// Driver function
int main()
{
    string S = "abbbc", T = "abc";
    int n = S.length(), m = T.length();
 
    // Function Call
    cout << maxCost(S, T, n, m);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Function to find the maximum
  // cost of a subsequence
  static int maxCost(String s, String t, int n, int m)
  {
    // mxCost stores the maximum
    // cost of a subsequence
    int mxCost = 0;
 
    // left[i] and right[i] store
    // the minimum and maximum
    // value of ai among all
    // valid a's respectively
    int []left = new int[m];
    int []right = new int[m];
 
    int j = 0;
    for (int i = 0; i < n; i++) {
      if (j >= m)
        break;
 
      if (s.charAt(i) == t.charAt(j)) {
        left[j] = i;
        j++;
      }
    }
 
    j = m - 1;
    for (int i = n - 1; i >= 0; i--) {
      if (j < 0)
        break;
 
      if (s.charAt(i) == t.charAt(j)) {
        right[j] = i;
        j--;
      }
    }
 
    for (int i = 0; i < m - 1; i++) {
      mxCost = Math.max(mxCost,
                        right[i + 1] - left[i]);
    }
 
    return mxCost;
  }
 
  // Driver function
  public static void main(String[] args)
  {
    String S = "abbbc", T = "abc";
    int n = S.length(), m = T.length();
 
    // Function Call
    System.out.print(maxCost(S, T, n, m));
  }
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to find the maximum
# cost of a subsequence
def maxCost(s, t, n, m):
     
    # mxCost stores the maximum
    # cost of a subsequence
    mxCost = 0
 
    # left[i] and right[i] store
    # the minimum and maximum
    # value of ai among all
    # valid a's respectively
    left = []
    right = []
 
    j = 0
    for i in range(0, n):
        if (j >= m):
            break
 
        if (s[i] == t[j]):
            left.append(i)
            j += 1
 
    j = m - 1
    for i in reversed(range(n)):
        if (j < 0):
            break
 
        if (s[i] == t[j]):
            right.append(i)
            j -= 1
 
    for i in range(0, m - 1):
        mxCost = max(mxCost, right[i + 1] - left[i])
 
    return mxCost
 
# Driver function
S = "abbbc"
T = "abc"
n = len(S)
m = len(T)
 
print(maxCost(S, T, n, m))
 
# This code is contributed by Samim Hossain Mondal.

// C# program for the above approach
using System;
class GFG{
 
  // Function to find the maximum
  // cost of a subsequence
  static int maxCost(String s, String t, int n, int m)
  {
 
    // mxCost stores the maximum
    // cost of a subsequence
    int mxCost = 0;
 
    // left[i] and right[i] store
    // the minimum and maximum
    // value of ai among all
    // valid a's respectively
    int []left = new int[m];
    int []right = new int[m];
 
    int j = 0;
    for (int i = 0; i < n; i++) {
      if (j >= m)
        break;
 
      if (s[i] == t[j]) {
        left[j] = i;
        j++;
      }
    }
 
    j = m - 1;
    for (int i = n - 1; i >= 0; i--) {
      if (j < 0)
        break;
 
      if (s[i] == t[j]) {
        right[j] = i;
        j--;
      }
    }
 
    for (int i = 0; i < m - 1; i++) {
      mxCost = Math.Max(mxCost,  right[i + 1] - left[i]);
    }
 
    return mxCost;
  }
 
  // Driver function
  public static void Main()
  {
    String S = "abbbc", T = "abc";
    int n = S.Length, m = T.Length;
 
    // Function Call
    Console.Write(maxCost(S, T, n, m));
  }
}
 
// This code is contributed by gfgking

<script>
    // JavaScript program for the above approach
 
    // Function to find the maximum
    // cost of a subsequence
    const maxCost = (s, t, n, m) => {
     
        // mxCost stores the maximum
        // cost of a subsequence
        let mxCost = 0;
 
        // left[i] and right[i] store
        // the minimum and maximum
        // value of ai among all
        // valid a's respectively
        let left = new Array(m).fill(0), right = new Array(m).fill(0);
 
        let j = 0;
        for (let i = 0; i < n; i++) {
            if (j >= m)
                break;
 
            if (s[i] == t[j]) {
                left[j] = i;
                j++;
            }
        }
 
        j = m - 1;
        for (let i = n - 1; i >= 0; i--) {
            if (j < 0)
                break;
 
            if (s[i] == t[j]) {
                right[j] = i;
                j--;
            }
        }
 
        for (let i = 0; i < m - 1; i++) {
            mxCost = Math.max(mxCost,
                right[i + 1] - left[i]);
        }
 
        return mxCost;
    }
 
    // Driver function
 
    let S = "abbbc", T = "abc";
    let n = S.length, m = T.length;
 
    // Function Call
    document.write(maxCost(S, T, n, m));
 
// This code is contributed by rakeshsahni
 
</script>

3

Tiempo Complejidad : O(n + m)
Espacio Auxiliar : O(n)