Find longest substring

Given a string and list of words, I want to find the longest substring such that it does not have any word present in the provided list of words.

Constraints:

The length of the string is 1 to 10^5, with no spaces
The size of the words list is 1 to 10, with no spaces, and each word length is in the range of 1 to 10.

Example:

s = "helloworld"
words = ["wor", "rld"]

Solution :

Valid longest substring: hellowo , here we don't have "wor", "rld" in this substring. 
Result = 7

Here is my code, which works fine for smaller inputs:

int solve(String s, List<String> list) {
	int answer = 0, j=0;
	for(int i = 0 ; i <= s.length(); i++) {
		String sub = s.substring(j, i);
		for(String e : list) {
			if(sub.contains(e)){
				j = j+1;
				sub = s.substring(j, i);
			}
		}
		answer = Math.max(answer, i-j);
	}
	return answer;
}

The time complexity for this code is I assume O(m*n^2) where n is the size of the input string and m is the size of the list.

How to reduce time complexity and solve this with a better approach.

Edit: Updated the time complexity based on meriton explanation.

Your complexity analysis is wrong, because substring and contains are not constant time operations, but depend upon the length of the strings involved.

Suppose the input string doesn't contain any search word. Then, you'll do substrings of length 1, 2, 3, ..., n, and call contains on each of them m times, for a total complexity of O(mn^2) ...

To get an actual O(mn) algorithm, I'd do something like this:

var answer = 0;
var j = 0;
for (int i = 0; i < s.length; i++) {
    while (endsWith(s, j, i, words) j++;
    answer = Math.max(answer, i - j);
}

where

/** @return whether s[begin..end] ends with a word in words */
boolean endsWith(String s, int begin, int end, List<String> words) {
    for (var word : words) {
        if (endsWith(s, begin, end, word)) {
            return true;
        }
    }
}

boolean endsWith(String s, int begin, int end, String word) {
    var offset = end - word.length;
    if (offset < begin) return false;
    for (int i = 0; i < word.length; i++) {
        if (s.charAt(offset + i) != word.charAt(i)) return false;
    }
    return true;
}

(this code is untested, you may have to fix minor bugs, but the general idea should be solid)

> Can you please share time complexity of this solution, I still see it as O(m*n^2)

endsWith is O(m), and invoked at most 2n times, because each invocation increases i or j, each of which is increased at most n times.

I believe it is solvable with O(N * max_word_length) (at least there no polynomial dependency on word count) TC using trie data structure:

public class SO76451768 {

    public int solve(String s, List<String> list) {
        Trie revert = new Trie(true);
        list.forEach(revert::add);

        char[] chars = s.toCharArray();

        int ans = 0;
        int start = 0;
        int end = 1;

        while (end <= chars.length) {
            int r = revert.matchLen(chars, start, end);
            if (r == 0) {
                ans = Math.max(ans, end - start);
                end++;
            } else {
                start = Math.max(start + 1, end - r + 1);
                end = start + 1;
            }
        }


        return ans;
    }


    static class Trie {

        final boolean revert;

        Trie[] children = new Trie[26];

        boolean eow;

        public Trie(boolean revert) {
            this.revert = revert;
        }

        int matchLen(char[] c, int from, int to) {
            Trie child;
            Trie[] arr = children;
            for (int i = 0; i < to - from; i++) {
                child = arr[c[revert ? to - i - 1 : i + from] - 'a'];
                if (child == null) {
                    return 0;
                }
                if (child.eow) {
                    return i + 1;
                }
                arr = child.children;
            }
            return 0;
        }

        void add(String key) {
            Trie child = null;
            Trie[] arr = children;
            char[] chars = key.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[revert ? chars.length - i - 1 : i];
                child = arr[c - 'a'];
                if (child == null) {
                    child = new Trie(revert);
                    arr[c - 'a'] = child;
                }
                arr = child.children;
            }
            child.eow = true;
        }
    }

}

Step 1: store words in a prefix tree (aka trie)

We can store words in a prefix tree (aka trie) as follows: The root node points to up to 26 nodes, one for the first letter of each word being stored. Then, each node points to up to 26 descendants, one for each letter than can follow the prefix from the root to the current node.

Example: we want to store CAT, CAN, COT, ART, ARE

           root
/    \
C      A
/ \     |
A   O    R
/ \  |   / \
N   T T  E   T

Put the list of words in a prefix tree. If a word is ever an extension of another word (e.g. catatonic vs cat), omit the longer word. I.e., in creating your tree, if a word ever ends on a letter with descendants, delete all descendants from the tree. If a word ever extends past a leaf, ignore it.

This step is O(sum of letter counts of forbidden words)

Step 2: find the starting and ending indices of banned words in the input string

Maintain a linked list of references/pointers to letters in the prefix tree, initially empty. I'll call these pointers below.

First, an example: Say the input string is CART, and the banned words are CAN, CAT, COT, ARE, ART as above.

parse C: create a new pointer to the 'C' child of the root
parse A: create a new pointer to the 'A' child of the root
update the 'C' pointer to point to its child 'A'
parse R: we don't create a new pointer since no banned word starts with 'R'
delete the pointer to the 'A' that has no 'R' child
update the pointer to the other 'A' to point to its R child
parse T: we don't create a new pointer since no banned word starts with 'R'
update the only remaining pointer to point to its 'T' child. Notice that this is a leaf 3 down from the root, so the end of a length 3 banned word. Store the pair of indices for later use.

Note that every single pointer will always point to the current letter. On every step, a pointer either:

1. moves to its child that matches the new letter
2. is deleted if no child matches the new letter
3. is created if the root has a child matching the new letter (i.e. if a banned word starts with the new letter)

Parse the input string. For each letter:

• for each pointer in your list of pointers, either 1) delete it if the current letter isn't a descendant, or point to the appropriate descendant if the current letter is a descendant.
• create a pointer to the current letter as the first letter of a word, if possible.
• if you reach the end of a word, then the last few characters in the string form a forbidden word. The character count is the depth in the prefix tree. Note the index where each word starts and ends.

This step is O((length of input string) * (average number of pointers)). I'm not sure how many pointers you're likely to have active at once.

Step 3: find the longest substring that doesn't contain the starting and ending indices of any banned word

Once this is done, in linear additional time you can use this to find the longest substring that doesn't contain a forbidden word.