Given a String and dictionary of words, break the string in minimum space sentence
Advice 1

You can get a substantial speed up by setting input = input.toLowerCase() and removing word = word.toLowerCase().

Advice 2

What comes to code, I suggest you separate the actual algorithm from the standard output. That way you can reuse your solution on larger string without getting overwhelmed with all the output. Also, it allows passing the result to some other processing routines, etc:

public static String[] opGetShortestTokenizationV2(String text,
                                                   Set&lt;String&gt; vocabulary) {
    text = text.toLowerCase();
    int left = 0;
    int right = text.length();
    List&lt;String&gt; result = new ArrayList&lt;&gt;();

    while (left &lt; right) {
        for (int i = 0; i &lt;= right; i++) {
            String word = text.substring(i, right);
            if (vocabulary.contains(word)) {
                right = i;
                result.add(word);
            }
        }
    }

    Collections.reverse(result);
    return result.toArray(new String[result.size()]);
}


Advice 3

left is not used. Your while loop condition becomes right != 0.