Given a String and dictionary of words, break the string in minimum space sentence.Ex: inputStr = ilikefacebook dictionary = {i,like,face,book,facebook} Possible Strings: i like face book - 3 spaces i like Facebook - 2 spaces - this is expected answer.Here's a trivial solution. It's a simple solution, but the runtime performance is poor O(n2). There must be better ways of doing this. public class MyClass {    public static void main(String[] args) {        String input = IlikeFacebook;        HashSet<String> dict = new HashSet<String>();        dict.add(i);        dict.add(like);        dict.add(face);        dict.add(book);        dict.add(facebook);        int left = 0;        int right = input.length();        int count = -1;        boolean[] status = new boolean[input.length()];        while (left < right) {            for (int i = 0; i <= right; i++) {                String word = input.substring(i, right);                word = word.toLowerCase();                if (dict.contains(word)) {                    count++;                    right = i;                    System.out.println( ->  + word);                }            }        }        System.out.println( Space count  + count);    }}Can anyone provide a better and efficient solution of this problem? 
Given a String and dictionary of words, break the string in minimum space sentence
java;performance;algorithm