Encuentre el índice de inicio mínimo de una substring de una string dada que contiene todas las palabras dadas de manera contigua

Dada una string S y una array de palabras de igual longitud (strings) arr[]. La tarea es encontrar el índice de inicio mínimo de la substring que contiene todas las palabras dadas de manera contigua . Si no se encuentra dicho índice, devuelve -1 .
Nota: Las palabras pueden estar en cualquier secuencia.

Ejemplos:

Entrada : arr[ ] = {“bat”, “bal”, “cat”}, S = “hellocatbyebalbatcatyo”
Salida : 11
Explicación : la substring que comienza en el índice 11 contiene las 3 palabras de manera contigua.

Entrada : arr[ ] = {“hat”, “mat”}, S = “aslkfndsuvbsdlvnsk”
Salida : -1
Explicación : No hay ninguna substring que contenga ambas palabras de manera contigua.

Enfoque: la tarea se puede resolver encontrando cualquiera de las palabras en el índice mínimo y luego simulando el proceso desde el índice final de la primera palabra para verificar si todas las demás palabras están presentes en posiciones contiguas o no.
Siga los pasos para resolver el problema:

• Guarde todas las palabras en un conjunto desordenado, digamos st, para buscar las palabras en tiempo constante.
• Recorra la string y verifique la substring comenzando en cada índice de longitud M (longitud de cada palabra), una vez que se encuentra una substring válida, que está presente en S, comience a simular el proceso después del índice final de la substring anterior y verifique si todas las demás palabras están presentes de manera contigua o no.
• Si todas las palabras se encuentran de forma contigua, devuelve el índice mínimo donde se encuentra, de lo contrario, devuelve -1.

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 min index
int minIndex(string arr[], string S, int N, int M)
{
    // Unordered set to store all words
    unordered_set<string> st;
 
    // Insert each word in the set
    for (int i = 0; i < N; i++)
        st.insert(arr[i]);
 
    // Traverse over the string s
    for (int i = 0; i < S.size() - M; i++) {
        // Substring to check whether
        // it is part of array of
        // words or not
        string x = S.substr(i, M);
 
        // Variables to check the condition, store the
        // index and keep count of words
        int p = 0, k = -1, d = N;
 
        // If substring is one of the words
        if (st.find(x) != st.end()) {
 
            // Store the index
            k = i;
 
            // Decrement d
            d--;
 
            // Check further
            for (int j = i + M; j < S.size() - M; j += M) {
 
                // Substring to check
                // whether it is part of
                // array of words or not
                string y = S.substr(j, M);
 
                // If substring is not part of word
                if (d == 0)
                    break;
                if (st.find(y) == st.end()) {
                    p = 1;
                    i = j - 1;
                    break;
                }
                d--;
            }
        }
 
        // If index is found, return the index
        if (p == 0 and k != -1)
            return k;
    }
 
    // If no index found, return -1
    return -1;
}
 
// Driver Code
int main()
{
 
    // Input
    string arr[] = { "bat", "bal", "cat" };
    string S = "hellocatbyebalbatcatyo";
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = arr[0].size();
 
    // Function call to find the minimum index
    cout << minIndex(arr, S, N, M);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the min index
static int minIndex(String arr[], String S, int N, int M)
{
   
    // Unordered set to store all words
    HashSet<String> st = new HashSet<String>();
 
    // Insert each word in the set
    for (int i = 0; i < N; i++)
        st.add(arr[i]);
 
    // Traverse over the String s
    for (int i = 0; i < S.length() - M; i++)
    {
       
        // SubString to check whether
        // it is part of array of
        // words or not
        String x = S.substring(i, i+M);
 
        // Variables to check the condition, store the
        // index and keep count of words
        int p = 0, k = -1, d = N;
 
        // If subString is one of the words
        if (st.contains(x)) {
 
            // Store the index
            k = i;
 
            // Decrement d
            d--;
 
            // Check further
            for (int j = i + M; j < S.length() - M; j += M) {
 
                // SubString to check
                // whether it is part of
                // array of words or not
                String y = S.substring(j, j+M);
 
                // If subString is not part of word
                if (d == 0)
                    break;
                if (!st.contains(y)) {
                    p = 1;
                    i = j - 1;
                    break;
                }
                d--;
            }
        }
 
        // If index is found, return the index
        if (p == 0 && k != -1)
            return k;
    }
 
    // If no index found, return -1
    return -1;
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Input
    String arr[] = { "bat", "bal", "cat" };
    String S = "hellocatbyebalbatcatyo";
    int N = arr.length;
    int M = arr[0].length();
    // Function call to find the minimum index
    System.out.print(minIndex(arr, S, N, M));
}
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to find the min index
def minIndex(arr, S, N, M):
   
   # Unordered set to store all words
    st = set(arr)
     
    # Insert each word in the set
    for i in range(len(S)-M):
        x = S[i: i+M]
         
         # Variables to check the condition, store the
        # index and keep count of words
        p = 0
        k = -1
        d = N
         
        # If substring is one of the words
        if x in st:
           
          # Store the index
            k = i
             
           # Decrement d
            d -= 1
             
            # Traverse over the string s
            for j in range(i+M, len(S)-M, M):
               
               # Substring to check
                # whether it is part of
                # array of words or not
                y = S[j: j+M]
                 
                # If substring is not part of word
                if d == 0:
                    break
                if y not in st:
                    p = 1
                    i = j-1
                    break
                d -= 1
                 
        # If index is found, return the index
        if p == 0 and k != -1:
            return k
           
    # If no index found return -1     
    return -1
 
# Driver code
arr = ["bat", "bal", "cat"]
S = "hellocatbyebalbatcatyo"
N = len(arr)
M = len(arr[0])
print(minIndex(arr, S, N, M))
 
# This code is contributed by parthmanchanda81

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the min index
static int minIndex(string []arr, string S, int N, int M)
{
    // Unordered set to store all words
    HashSet<string> st = new HashSet<string>();
 
    // Insert each word in the set
    for (int i = 0; i < N; i++)
        st.Add(arr[i]);
 
    // Traverse over the string s
    for (int i = 0; i < S.Length - M; i++) {
        // Substring to check whether
        // it is part of array of
        // words or not
        string x = S.Substring(i, M);
 
        // Variables to check the condition, store the
        // index and keep count of words
        int p = 0, k = -1, d = N;
 
        // If substring is one of the words
        if (st.Contains(x)) {
 
            // Store the index
            k = i;
 
            // Decrement d
            d--;
 
            // Check further
            for (int j = i + M; j < S.Length - M; j += M) {
 
                // Substring to check
                // whether it is part of
                // array of words or not
                string y = S.Substring(j, M);
 
                // If substring is not part of word
                if (d == 0)
                    break;
                if (st.Contains(y)==false) {
                    p = 1;
                    i = j - 1;
                    break;
                }
                d--;
            }
        }
 
        // If index is found, return the index
        if (p == 0 && k != -1)
            return k;
    }
 
    // If no index found, return -1
    return -1;
}
 
// Driver Code
public static void Main()
{
 
    // Input
    string []arr = { "bat", "bal", "cat" };
    string S = "hellocatbyebalbatcatyo";
    int N = arr.Length;
    int M = arr[0].Length;
 
    // Function call to find the minimum index
    Console.Write(minIndex(arr, S, N, M));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
// Javascript program for the above approach
 
// Function to find the min index
function minIndex(arr, S, N, M) {
  // Unordered set to store all words
  let st = new Set();
 
  // Insert each word in the set
  for (let i = 0; i < N; i++) st.add(arr[i]);
 
  // Traverse over the string s
  for (let i = 0; i < S.length - M; i++) {
    // Substring to check whether
    // it is part of array of
    // words or not
    let x = S.substr(i, M);
    console.log(x);
    // Variables to check the condition, store the
    // index and keep count of words
    let p = 0,
      k = -1,
      d = N;
 
    // If substring is one of the words
    if (st.has(x)) {
      // Store the index
      k = i;
 
      // Decrement d
      d--;
 
      // Check further
      for (let j = i + M; j < S.length - M; j += M) {
        // Substring to check
        // whether it is part of
        // array of words or not
        let y = S.substr(j, M);
 
        // If substring is not part of word
        if (d == 0) break;
        if (!st.has(y)) {
          p = 1;
          i = j - 1;
          break;
        }
        d--;
      }
    }
 
    // If index is found, return the index
    if (p == 0 && k != -1) return k;
  }
 
  // If no index found, return -1
  return -1;
}
 
// Driver Code
 
// Input
let arr = ["bat", "bal", "cat"];
let S = "hellocatbyebalbatcatyo";
let N = arr.length;
let M = arr[0].length;
 
// Function call to find the minimum index
document.write(minIndex(arr, S, N, M));
 
// This code is contributed by _saurabh_jaiswal.
</script>

11

Complejidad de tiempo : O(S*M), S es la longitud de la string y M es la longitud de cada palabra
Espacio auxiliar : O(N), N es el número de palabras