2781. Length of the Longest Valid Substring

Goal

https://leetcode.com/problems/length-of-the-longest-valid-substring/description/

You are given a string word and an array of strings forbidden.

A string is called valid if none of its substrings are present in forbidden.

Return the length of the longest valid substring of the string word.

A substring is a contiguous sequence of characters in a string, possibly empty.

Example 1:

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
Output: 4
Explanation: There are 11 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" and "aabc". The length of the longest valid substring is 4. 
It can be shown that all other substrings contain either "aaa" or "cb" as a substring.

Example 2:

Input: word = "leetcode", forbidden = ["de","le","e"]
Output: 4
Explanation: There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "de", "le", or "e" as a substring.

Constraints:

• 1 <= word.length <= 105
• word consists only of lowercase English letters.
• 1 <= forbidden.length <= 105
• 1 <= forbidden[i].length <= 10
• forbidden[i] consists only of lowercase English letters.

Approach#1: Bruteforce approach (TLE)

1. For each substring of a word
2. Check if each substring, again find all possible substrings and check if that exists in forbidden . If it does then the substring is invalid. If it doesn’t then update the global answer.
3. The time complexity of code is O(n^4)

Following is the code to implement this.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = new Set(forbidden);
    const n = word.length;
    let ans = 0;
    const isValid = w => {
        const m = w.length;
        for (let i = 0; i < m; i++) {
            for (let j = i; j < m; j++) {
                const sub = w.substring(i, j + 1);
                if (set.has(sub)) {
                    return false;
                }
            }
        }
        return true;
    }
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const sub = word.substring(i, j + 1);
            if (isValid(sub)) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Approach#2: Using dynamic programming (OOM)

1. We can leverage the fact that if a big substring contains any small invalid substring then entire substring will be invalid.
2. It means we can store the result for each substring and reuse when we check the bigger substring.
3. We will use range DP form.
4. We can come up with following recursion relationship

f(i,j) - true if substring is valid otherwise false
ixxxxxj
f(i,j) = f(i+1,j) && f(i,j-1) && !forbidden.has(sub[i,j])

Q. How to build DP table?

1. Lower diagonal represent i > j which is invalid so we can ignore.
2. Diagonal represent single char so it can be a base case
3. Each cell depends on bottom and left value
4. So we can start traversing i from (m-1,0)
5. Then j from i to m-1

Following is code for reference.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = forbidden.reduce((acc, w) => { acc.add(w); return acc; }, new Set());
    const m = word.length;
    const dp = new Array(m).fill(0).map(a => new Array(m).fill(false));
    let ans = 0;
    // base case: (i==j)
    for (let i = 0; i < m; i++) {
        dp[i][i] = !set.has(word.substring(i, i + 1));
        if (dp[i][i]) {
            ans = 1;
        }
    }
    for (let i = m - 2; i >= 0; i--) {
        for (let j = i + 1; j < m; j++) {
            const w = word.substring(i, j + 1);
            dp[i][j] = dp[i + 1][j] && dp[i][j - 1] && !set.has(w);
            if (dp[i][j]) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Time complexity: O(m*m)

Space complexity: O(m*m)

Above code throws heap out of memory due to our dp array size.

There is another way to build table as well which is length basis. We can start scanning len=2……m. Following is code for reference.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = forbidden.reduce((acc, w) => { acc.add(w); return acc; }, new Set());
    const m = word.length;
    const dp = new Array(m).fill(0).map(a => new Array(m).fill(false));
    let ans = 0;
    // base case: (i==j)
    for (let i = 0; i < m; i++) {
        dp[i][i] = !set.has(word.substring(i, i + 1));
        if (dp[i][i]) {
            ans = 1;
        }
    }
    for (let len=2; len <=m; len++) {
        for (let i=0; i < m - len + 1; i++) {
            const j = i + len - 1;
            const w = word.substring(i, j + 1);
            dp[i][j] = dp[(i + 1)][j] && dp[i][j - 1] && !set.has(w);
            if (dp[i][j]) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Approach#3: Dynamic programming with optimized space (TLE)

Since f(i,j) only depends on previous diagonal value therefore we can simply use the 2*m size dp array. Following is updated code for reference.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = forbidden.reduce((acc, w) => { acc.add(w); return acc; }, new Set());
    const m = word.length;
    // 2* m size
    const dp = new Array(2).fill(0).map(a => new Array(m).fill(false));
    let ans = 0;
    // base case: (i==j)
    for (let i = 0; i < m; i++) {
        dp[i%2][i] = !set.has(word.substring(i, i + 1));
        if (dp[i%2][i]) {
            ans = 1;
        }
    }
    for (let i = m - 2; i >= 0; i--) {
        for (let j = i + 1; j < m; j++) {
            const w = word.substring(i, j + 1);
            dp[i%2][j] = dp[(i + 1)%2][j] && dp[i%2][j - 1] && !set.has(w);
            if (dp[i%2][j]) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Time complexity: O(m*m)

Space complexity: O(m)

Following is code using length base traversal.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = forbidden.reduce((acc, w) => { acc.add(w); return acc; }, new Set());
    const m = word.length;
    // 2* m size
    const dp = new Array(2).fill(0).map(a => new Array(m).fill(false));
    let ans = 0;
    // base case: (i==j)
    for (let i = 0; i < m; i++) {
        dp[i%2][i] = !set.has(word.substring(i, i + 1));
        if (dp[i%2][i]) {
            ans = 1;
        }
    }
    for (let len=2; len <=m; len++) {
        for (let i=0; i < m - len + 1; i++) {
            const j = i + len - 1;
            const w = word.substring(i, j + 1);
            dp[i%2][j] = dp[(i + 1)%2][j] && dp[i%2][j - 1] && !set.has(w);
            if (dp[i%2][j]) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Approach #4: Right to left scan (TLE)

1. Instead of traversing from left to right, we can traverse from right to left.
2. right can represent the string ending at.
3. We can traverse left from right to 0
4. This gives as part of the string from [left,right] and we need to check if adding left char still keeps [left, right] a valid substring or not.
5. We can check all possible substrings from k=left to right and every substring [left, k] check if it is valid or not.
6. If valid then update the global answer ans = Math.max(ans, right — left + 1 .
7. If [left,k] does exist in the forbidden list then it means [k,right] substring can be discarded. This is bcz at kth we found that including kth made [left, right] invalid.
8. At this point, we can shift right to k-1 and break the loop to check the rest of k as the substring [left, right]will stay invalid.
9. Time complexity would be O(n^2)

Following is the code to implement it.

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = new Set(forbidden);
    const m= word.length;
    let ans = 0;
    let right = m- 1;
    for (let left = right; left >= 0; left--) {
        // Verify string (left, right) as ans zone
        for (let k = left; k <= right; k++) {
            const w = word.substring(left, k + 1);
            if (set.has(w)) {
                right = k - 1;
                break;
            }
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

Time complexity: O(m*m)

This still throws TLE.

Approach#5: Use the given limit on forbidden[i] ≤ 10 (Works)

1. As per the problem, the forbidden word can be at most of size 10.
2. It means when we are exploring [left,right] (which is testing of adding left char will keep the substring still valid or not) k can max go left, left+10 .
3. The time complexity of the code would be O(n*10)

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function (word, forbidden) {
    const set = new Set(forbidden);
    const n = word.length;
    let ans = 0;
    let right = n - 1;
    for (let left = right; left >= 0; left--) {
        // Verify string (left, right) as ans zone
        for (let k = left; k <= Math.min( left + 10, right); k++) {
            const w = word.substring(left, k + 1);
            if (set.has(w)) {
                right = k - 1;
                break;
            }
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

Can we apply forbidden limit on DP?

No. Our DP approach is working on sub problem size. f(i,j) doesn’t goes through each possible substring, instead it simply try to add a new char on the left or on the right.

Happy coding :-)