Keywords

                     Keywords
Given a paragraph of space-separated lowercase English words and a list of unique lowercase English keywords, find the minimum length of the substring of which contains all the keywords that are separated by space in any order. 
Note: The keywords should be space separated words but can occur in any order in the substring.

Input Format

The first line of the input consists of a single string denoting the paragraph. 
The second line contains an integer, which is the number of keywords that will be given. 
The -th of the next lines contains a lowercase English word.
Constraints
  • All the keywords are unique.
Output Format
Print in a single line, the minimum length of a substring of paragraph which contains all the keywords separated by space in any order. If all the keywords aren't present in the paragraph, then print.
Sample Input 0
why how whywhat why what how what when what
3
why
how
what
Sample Output 0
12
Explanation 0
The highlighted text shows the minimum sub string with all three keywords: why how why what whywhat how what when what.
Therefore the length of the minimum sub string is 12.
Note that the sub string whywhat neither contains the keyword why nor what as the keywords should be present as a whole string and not as part of a sub string.
Sample Input 1
why how what how when how when what
2
what
when
Sample Output 1
9
Explanation 1
The highlighted text shows the minimum sub string with the two keywords: why how what how when how when what.
Therefore the length of the minimum sub string is 9.

Code:

import java.io.*;
import java.lang.*;
import java.util.*;

public class Solution {

public int minimumLength(String text, ArrayList < String > keys) {

        int answer = 10000000;
        text += " $";
        for(int i = 0; i < text.length(); i++) 
        {
           ArrayList< String > dup = new ArrayList<String>(keys);
           String word = "";
           if(i > 0 && text.charAt(i - 1) != ' ')
               continue;
           for(int j = i; j < text.length(); j++) 
           {
                if(text.charAt(j) == ' ') 
                {
                    for(int k = 0; k < dup.size(); k++) 
                    {
                        if(dup.get(k).equals(word)) 
                        {
                              dup.remove(k);
                        }
                    }
                    word = "";
                }
                else 
                    word += text.charAt(j);
                if(dup.isEmpty()) 
                {
                    answer = Math.min(answer, j - i);
                    break;
                }
           }
        }
        if(answer == 10000000)
           answer = -1;

        return answer;
}

public static void main(String []args) {

      Solution s = new Solution();
      String text, buf;
      ArrayList < String > keys = new ArrayList < String >();
      Scanner in = new Scanner(System.in);
      text = in.nextLine();
      int keyWords = in.nextInt();
      in.nextLine();
      for(int i = 0; i < keyWords; i++) 
      {
         buf = in.nextLine();
         keys.add(buf);
      }
      System.out.println(s.minimumLength(text, keys));
    }
}

 

Coming soon...
Please do comment If u have any Queries!

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *