Length of the Longest Valid Substring - Practice Coding Problems

Length of the Longest Valid Substring - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "cbaaaabc", forbidden = ["aaa", "cb"]

› Output: 4

💡 Note: Valid substrings include "c", "b", "a", "aa", "aaaa", "b", "c", "ba", "bc". The longest is "aaaa" with length 4. Substrings containing "aaa" or "cb" are invalid.

Example 2 — No Forbidden

$ Input: word = "leetcode", forbidden = []

› Output: 8

💡 Note: Since no strings are forbidden, the entire string "leetcode" is valid with length 8.

Example 3 — All Invalid

$ Input: word = "aab", forbidden = ["a"]

› Output: 1

💡 Note: Only valid substring is "b" since any substring containing "a" is forbidden. Maximum length is 1.

Constraints

1 ≤ word.length ≤ 10⁴
0 ≤ forbidden.length ≤ 10⁵
1 ≤ forbidden[i].length ≤ 10
word and forbidden[i] consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

String 'cbaaaabc' with forbidden ['aaa', 'cb']

Process

Find all valid substrings avoiding forbidden ones

Output

Length 4 for longest valid substring 'aaaa'

Key Takeaway

🎯 Key Insight: Use sliding window to find maximum valid substring length while avoiding forbidden patterns

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use a sliding window approach where we check each possible starting position and expand as far as possible without including forbidden substrings. The optimal approach uses efficient string matching to find the longest valid substring. Best approach is sliding window with hash set lookup. Time: O(n² × m × k), Space: O(m × k)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n² × m × k)	O(m × k)	Use two pointers to maintain a valid window
Brute Force	O(n³ × m × k)	O(m × k)	Check all possible substrings for validity

Sliding Window — Algorithm Steps

Step 1: Use two pointers (left, right) to maintain window
Step 2: Expand right pointer and check for forbidden substrings
Step 3: When forbidden found, move left pointer past the forbidden substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Window

Begin with left pointer at start

Expand Right

Extend right pointer while valid

Contract on Invalid

Move left pointer when forbidden found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char* word, char forbidden[][100], int forbiddenSize) {
    int maxLength = 0;
    int n = strlen(word);
    
    for (int left = 0; left < n; left++) {
        for (int right = left; right < n; right++) {
            bool hasForbidden = false;
            
            // Check all substrings of current window
            for (int i = left; i <= right && !hasForbidden; i++) {
                for (int j = i; j <= right; j++) {
                    int currentLen = j - i + 1;
                    char temp[1001];
                    strncpy(temp, word + i, currentLen);
                    temp[currentLen] = '\0';
                    
                    for (int f = 0; f < forbiddenSize; f++) {
                        if (strcmp(temp, forbidden[f]) == 0) {
                            hasForbidden = true;
                            break;
                        }
                    }
                    if (hasForbidden) break;
                }
            }
            
            if (hasForbidden) {
                break; // No need to expand further from this left
            } else if (right - left + 1 > maxLength) {
                maxLength = right - left + 1;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char word[1001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    char line[10001];
    fgets(line, sizeof(line), stdin);
    
    char forbidden[100][100];
    int forbiddenSize = 0;
    
    // Simple JSON array parsing
    char* token = strtok(line, "[],\"");
    while (token != NULL && forbiddenSize < 100) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(forbidden[forbiddenSize++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    printf("%d\n", solution(word, forbidden, forbiddenSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m × k)

For each position, we may check O(n) substrings against m forbidden strings of length k

⚠ Quadratic Growth

Space Complexity

O(m × k)

Hash set to store forbidden strings

✓ Linear Space

34.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler