Finding the shortest substring containing keywords

Question

Problem: Write a function that takes a String document and a String[] keywords and returns the smallest substring of document that contains all of the strings in keywords.

Notes:

• document will contain at least 1 word
• document will separate words by a single space
• A word can only contain [a-z] and can appear multiple times in the document
• keywords will be a distinct list of words
• Matches must be perfect (ie bat and batman do not match)
• If there are multiple shortest substrings, pick the first one
• keywords can appear in the substring in any order
• The substring length is counted in words, not characters
• Must be written in Java 7 and provide a class called Solution with a method solution

Examples

Input:

document: "a b c d a"
keywords: ["a", "c", "d"]

Output: "c d a"

Input:

document: "world there hello hello where world"
keywords: ["hello", "world"]

Output: "world there hello"

My attempt:

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
    private Map<String, Integer> snippetDataPoints = new HashMap<String, Integer>();
    private String[] words, searchTerms;
    private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;

    public static String solution(String document, String[] searchTerms) {
        Solution solution = new Solution (document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
        return solution.solve();
    }

    private Solution(String[] words, String[] searchTerms){
        this.words = words;
        this.searchTerms = searchTerms;
        shortestSnippetEnd=words.length;
    }

    private String solve(){
        for(int i=0;i<words.length;i++){
            if(searchTermsContains(words[i])){
                addToSnippet(words[i], i);
            }
        }
        StringBuilder snippet = new StringBuilder();
        for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){
            snippet.append(words[i] + " ");
        }
        snippet.deleteCharAt(snippet.length()-1);
        return snippet.toString();
    }

    private void addToSnippet(String word, int position) {
        Integer previousPosition = snippetDataPoints.put(word, position);
        if(previousPosition == null || previousPosition <= currentSnippetStart){
            currentSnippetStart = Collections.min(snippetDataPoints.values());
        }
        if(snippetDataPoints.size() == searchTerms.length){
            determineShortestSnippet(position);
        }
    }

    private void determineShortestSnippet(int currentPositionEnd) { 
        if(shortestSnippetEnd - shortestSnippetStart > currentPositionEnd - currentSnippetStart ){
            shortestSnippetStart = currentSnippetStart;
            shortestSnippetEnd = currentPositionEnd;
        }
    }

    private boolean searchTermsContains(String word) {
        for(String searchTerm : searchTerms){
            if(searchTerm.equals(word)) return true;
        }
        return false;
    }
}

My Analysis: This was written with a time constraint, so it manages to keep simplicity without losing too much efficiency. The document.split() is unnecessary - I could have done the parsing on the fly, but it would have been more complicated. Similarly, I could have created a better implementation of searchTermsContains, perhaps using a tree of character nodes to minimize search time. However, it would be really great if I could significantly reduce the usage of searchTermsContains altogether since its adding a wsto my time complexity, but I cant think of anyway.

I also could have used a more efficient data structure for the snippetDataPoints. I think a parallel array would have worked just as well and used significantly less memory (though still technically O(s)?). And finally, a lot of my code runs under the assumption that all input is perfectly valid - something Im willing to accept given time constraints and the nature of the problem.

Answer 1

Problems / Bugs

• The following calls will all throw an ArrayIndexOutOfBoundsException

  String document = "a b c d";
  System.out.println(Solution.solution(document, new String[]{"g"}));
  System.out.println(Solution.solution(document, new String[]{"g", "a", "s", "s"}));
  System.out.println(Solution.solution(document, new String[]{"a", "b" ,"c", "d"}));
  

  because of

  for (int i = shortestSnippetStart; i <= shortestSnippetEnd; i++) {
  

  Assuming you have fixed the above by changing to

  for (int i = shortestSnippetStart; i < shortestSnippetEnd; i++) {
  

  The above calls will return

  a b c d
  a b c d
  a b c

• The following will throw an exception if snippet.length==0

  snippet.deleteCharAt(snippet.length()-1);  
  

General

• you shouldn't do string concatenation inside StringBuilder.append() method. The append() method returns a StringBuilderso you should just stack the calls like

  snippet.append(words[i])
         .append(" ");
  

• you shouldn't declare multiple variables in a single line, because this removes readability of the code.

• give your conditions/variables the possibility to breathe

  for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){  
  

  should be

  for(int i = shortestSnippetStart; i <= shortestSnippetEnd; i++) {