Length of the Longest Valid Substring

Hard
1264.

Length of the Longest Valid Substring

Length of the Longest Valid Substring is a hard coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

A chat filter on CodeKairo blocks a list of forbidden strings. A string is valid if none of its substrings is in forbidden.

Given word and forbidden, return the length of the longest valid substring of word. The empty substring is valid, so the answer may be 0.

Example 1

Input
word = "kairokai", forbidden = ["ok","ai"]
Output
3
Explanation
`iro` avoids both; any longer window contains `ai` or `ok`.

Example 2

Input
word = "codekairo", forbidden = ["z"]
Output
9

Example 3

Input
word = "aaaa", forbidden = ["a"]
Output
0

Constraints

  • 1 <= word.length <= 10^5
  • word consists only of lowercase English letters
  • 1 <= forbidden.length <= 10^5
  • 1 <= forbidden[i].length <= 10
  • forbidden[i] consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
var longestValidSubstring = function(word, forbidden) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Length of the Longest Valid Substring — Problem & Solution

Length of the Longest Valid Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Length of the Longest Valid Substring is a hard coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

Problem statement

A chat filter on CodeKairo blocks a list of forbidden strings. A string is valid if none of its substrings is in forbidden.

Given word and forbidden, return the length of the longest valid substring of word. The empty substring is valid, so the answer may be 0.

Example 1

Input: word = "kairokai", forbidden = ["ok","ai"]
Output: 3
Explanation: `iro` avoids both; any longer window contains `ai` or `ok`.

Example 2

Input: word = "codekairo", forbidden = ["z"]
Output: 9

Example 3

Input: word = "aaaa", forbidden = ["a"]
Output: 0

Constraints

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

Hints for Length of the Longest Valid Substring

  1. Hint 1

    Validity is monotone: if a window is valid, every window inside it is valid. Think sliding window — for each right end, find the smallest valid left end.

  2. Hint 2

    When the right end moves to r, the only new substrings are those ending at r, and a forbidden word has length at most 10, so only 10 of them can matter.

  3. Hint 3

    Put forbidden in a hash set. For i from r down to max(left, r - 9), if word[i..r] is forbidden, move left to i + 1 and stop. The window [left, r] is then the longest valid one ending at r.

How to solve Length of the Longest Valid Substring

Sweep the right end of a window. A newly appearing forbidden substring must end at the new right end and is at most 10 long, so each step needs at most 10 hash-set lookups to push the left end past every forbidden occurrence.

Approach

  1. Insert all forbidden strings into a hash set; set left = 0, best = 0.
  2. For each r from 0 to n - 1: for i from r down to max(left, r - 9), if word[i..r] is in the set, set left = i + 1 and break.
  3. Update best = max(best, r - left + 1).
  4. Return best.

Why it works

Invariant: [left, r] is the longest valid window ending at r. Moving to r + 1 can only introduce forbidden substrings that end at r + 1; scanning start positions from right to left finds the one with the largest start first, and the window must begin after it. Starts before left need not be checked because left already excludes an earlier forbidden occurrence. Valid windows are closed under shrinking, so the best window for each right end is the one starting at left.

Complexity

  • Time — O(n · 10 · 10) — at most 10 lookups of strings of length at most 10 per position
  • Space — O(total length of forbidden)

Pitfalls

  • Scanning i from left to right stops at the wrong forbidden substring and leaves the window invalid.
  • Starting the scan below left is wasted work; starting below r - 9 is pointless because forbidden words are at most 10 long.
  • Checking every substring of word against every forbidden word is far too slow.

Reference solution

Python

from typing import List

def longestValidSubstring(word: str, forbidden: List[str]) -> int:
    bad = set(forbidden)
    left = 0
    best = 0
    for r in range(len(word)):
        for i in range(r, max(left, r - 9) - 1, -1):
            if word[i:r + 1] in bad:
                left = i + 1
                break
        best = max(best, r - left + 1)
    return best

Java

public static int longestValidSubstring(String word, String[] forbidden) {
    Set<String> bad = new HashSet<>(Arrays.asList(forbidden));
    int left = 0, best = 0;
    for (int r = 0; r < word.length(); r++) {
        for (int i = r; i >= Math.max(left, r - 9); i--) {
            if (bad.contains(word.substring(i, r + 1))) {
                left = i + 1;
                break;
            }
        }
        best = Math.max(best, r - left + 1);
    }
    return best;
}

C++

int longestValidSubstring(string word, vector<string>& forbidden) {
    unordered_set<string> bad(forbidden.begin(), forbidden.end());
    int left = 0, best = 0, n = word.size();
    for (int r = 0; r < n; r++) {
        for (int i = r; i >= max(left, r - 9); i--) {
            if (bad.count(word.substr(i, r - i + 1))) {
                left = i + 1;
                break;
            }
        }
        best = max(best, r - left + 1);
    }
    return best;
}

JavaScript

var longestValidSubstring = function(word, forbidden) {
    var bad = new Set(forbidden);
    var left = 0, best = 0;
    for (var r = 0; r < word.length; r++) {
        for (var i = r; i >= Math.max(left, r - 9); i--) {
            if (bad.has(word.substring(i, r + 1))) {
                left = i + 1;
                break;
            }
        }
        best = Math.max(best, r - left + 1);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings