Given a string S and an array of equal length words (strings) arr[]. The task is to find the minimum start index of the substring that contains all the given words in a contiguous manner. If no such index is found, return -1.
Note: The words can be in any sequence.
Examples:
Input: arr[ ] = {“bat”, “bal”, “cat”}, S = “hellocatbyebalbatcatyo”
Output: 11
Explanation: Substring starting at index 11 contains all the 3 words in contiguous manner.Input: arr[ ] = {“hat”, “mat”}, S = “aslkfndsuvbsdlvnsk”
Output: -1
Explanation: There is no substring that contains both the words in a contiguous manner.
Approach: The task can be solved by finding any of the words at the minimum index, and then simulating the process from the end index of the first word to check whether all other words are present at contiguous positions or not.
Follow the steps to solve the problem:
- Store all the words in an unordered set say st, to look-up the words in constant time.
- Traverse the string and check substring starting at each index of length M (length of each word), once a valid substring is found, that is present in S, start simulating the process after the end index of previous substring and check whether all other words are present in contiguous manner or not.
- If all words are found in contiguous manner, return the minimum index where it is found, else return -1.
Below is the implementation of the above approach:
C++14
// 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
// 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 |
Python3
# 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#
// 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. |
Javascript
<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
Time Complexity: O(S*M), S is length of string and M is length of each word
Auxiliary Space: O(N), N is number of words
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!