CareerCup

The solution for the problem is to find the min Window from indexes i to j in text such that all target keywords are present and distance from i to j is minimal.

One approach is to start a sliding window mechanism with the help of a Queue and for every keyword found check if head of queue (first inserted keyword in window) is equal to new found keyword, if so remove the keyword from head and place it in the tail of queue. This way will allow the algorithm to test for all windows of matches found for every keyword, and in the end returning the min. Window size.

Implementation of the above algorithm in Scala:

object MinKWindowSum {
  def main(args: Array[String]): Unit = {   
    
    val document = "This Hello is a huge text with thousands of Hello words and other lines and World and many other Hello docs Words of World in many langs and features"    
    println(getMinWindowSize(document, "Hello World"))
  }   
    
  def getMinWindowSize(doc:String, s:String): Int = {
    
    val keywords = s.split(" ").toSet
    val idxs = keywords.map(k => (k -> ("(?i)\\Q" + k + "\\E").r.findAllMatchIn(doc).map(_.start)))
    .map{ case (keyword,itr) => itr.foldLeft(List[(String,Int)]())((result, num) => result :+ (keyword, num))}
    .foldLeft(List[(String,Int)]())((res, list) => res ++ list)
    .sortBy(_._2)
        
    var min = Int.MaxValue    
    var minI = 0
    var minJ = 0
    var currWindow = ListBuffer[(String,Int)]()
    
    for( tuple <- idxs ) {  
      if (!currWindow.isEmpty && currWindow.head._1.equals(tuple._1)) currWindow.remove(0)         
      currWindow += tuple
      if (keywords.subsetOf(currWindow.map(_._1).toSet)) {
        val currMin = currWindow.last._2 - currWindow.head._2 + currWindow.last._1.length
        if (min > currMin) {
          min = currMin
          minI = currWindow.head._2
          minJ = currWindow.last._2          
        }
      }      
    }
        
    println("min = " + min + " ,i = " + minI + " j = " + minJ )    
    min
  }
}
/*
input:
This Hello is a huge text with thousands of Hello words and other lines and World and many other Hello docs Words of World in many langs and features

output:
min = 25 ,i = 97 j = 117
*/

Pseudocode :

StringBuffer = null;

loop (until the list is empty) {

If word found -> Remove from list

Add the read string to buffer
}

O(N*M) SOLN:

import java.io.*;

class GFG {
	public static void main (String[] args) {
		//code
		String s1="HELLO";
		String s2="GEEK";
		
		int dp[][]=new int[s1.length()+1][s2.length()+1];
		int n=s1.length();
		int m=s2.length();
		for(int i=1;i<=n;i++)
		{
		    for(int j=1;j<=m;j++)
		    {
		        if(s1.charAt(i-1)==s2.charAt(j-1))
		        dp[i][j]=dp[i-1][j-1]+1;
		        else
		        dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
		        
		    }
		}
		//System.out.println(dp[n][m]);
		String make="";
		
		int x=n,y=m;
		while(x>0&&y>0)
		{
		    if(dp[x][y]==dp[x-1][y])
		    x--;
		    else if(dp[x][y]==dp[x][y-1])
		    y--;
		    else
		    {
		        x--;
		        y--;
		        make=s1.charAt(x)+make;
		    }
		}
		//System.out.println(make);
		
		int ptr=0;
		int i=0,j=0;
		String res="";
		while(ptr<make.length())
		{
		    while(s1.charAt(i)!=make.charAt(ptr))
		    res=res+s1.charAt(i++);
		    while(s2.charAt(j)!=make.charAt(ptr))
		    res=res+s2.charAt(j++);
		    res=res+make.charAt(ptr++);
		    i++;j++;
		}
		while(i<n)
		res=res+s1.charAt(i++);
		
		while(j<m)
		res=res+s2.charAt(j++);
		System.out.println(res);
		
	}
}

@ shikhar.00778 what happens when we have a list of words like :

{ "this" , "is", "probably", "a" ,  "bad", "idea" , 
   "to", "think" , "the" , "problem" , "in", "this" , "way" }

?

* Mark every word in synopsis with an ordinal #. Or store synopsis in a container with an index into words.
* Pick a word from the given list and find all occurrences of the word. Note the ordinal numbers of these occurrences.
* Repeat previous step for all the words in the list
* Find the minimal range of ordinal numbers which contains all the words.

Example:

word1: 2, 4, 8
word2: 5, 9
word3: 7

Look for shortest range: [2,5,7], [2,7,9] [4,5,7] [4,7,9] [5,7,8] [7,8,9]

Clearly [7,8,9] range (= 3) is the shortest substring.

Single pass algorithm

#include <algorithm>
#include <list>
#include <numeric>
#include <regex>
#include <string>
#include <sstream>
#include <unordered_map>
#include <iostream>

int main()
{
	std::string text( "hi 123 hi 12345 hello 123 world 1 hi 1 world 12 hello 123 hi etc" ); // T

	std::list<std::string> words = { "hi", "hello", "world" }; // W

	std::string word_regex_str;
	for (const auto& word : words) {
		if (!word_regex_str.empty()) word_regex_str += "|";
		word_regex_str += word;
	}
	std::regex word_regex(word_regex_str); // O(W)

	int best_start = 0;
	int best_len = 0;
	
	int matched_words_num = 0;
	std::unordered_map<std::string, int> word_counts;
	std::list<std::smatch> matches;

	for (auto match = std::sregex_iterator(text.begin(), text.end(), word_regex); // O(T)
			match != std::sregex_iterator();
			++match) {

		// add the new match
		matches.push_back(*match);

		auto word = match->str();
		if (++word_counts[word] == 1 && ++matched_words_num == words.size()) { // full match
			auto start = matches.front().position();
			auto end = matches.back().position() + matches.back().length();
			if (!best_len || end - start < best_len) {
				best_start = start;
				best_len = end - start;
			}

			// pop first matched word
			if (--word_counts[matches.front().str()] == 0)
				--matched_words_num;
			matches.pop_front();
		}

		// pop words matched later
		while (word_counts[matches.front().str()] > 1) {
			--word_counts[matches.front().str()];
			matches.pop_front();
		}
	}

	std::cout << text.substr(best_start, best_len) << std::endl;

    return 0;
}