Length Of the Valid Substring Program In java

Example:

Input: word = “cbaaaabc”, forbidden = [“aaa”,”cb”] Output: 4

Certainly! Let’s break down the problem and then provide a Java solution:

Problem Explanation:

You are given a string word and an array of strings forbidden. You need to find the length of the longest valid substring of word, where a substring is considered valid if none of its substrings are present in the forbidden array.

Example Explanation:

For the given example, word = "cbaaaabc" and forbidden = ["aaa", "cb"], we can identify the valid substrings as follows:

• “c”
• “b”
• “a”
• “ba”
• “aa”
• “bc”
• “baa”
• “aab”
• “ab”
• “abc”
• “aabc”

The longest valid substring is “baa” with a length of 4, as all other substrings contain either “aaa” or “cb” as a substring.

public class LongestValidSubstring {
    public int longestValidSubstring(String word, String[] forbidden) {
        int maxLen = 0;
        Set<String> forbiddenSet = new HashSet<>(Arrays.asList(forbidden));

        for (int i = 0; i < word.length(); i++) {
            for (int j = i + 1; j <= word.length(); j++) {
                String substring = word.substring(i, j);
                if (!containsForbidden(substring, forbiddenSet)) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }

        return maxLen;
    }

    private boolean containsForbidden(String substring, Set<String> forbiddenSet) {
        for (String forbidden : forbiddenSet) {
            if (substring.contains(forbidden)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String word = "cbaaaabc";
        String[] forbidden = {"aaa", "cb"};
        int maxLength = solution.longestValidSubstring(word, forbidden);
        System.out.println("Length of the longest valid substring: " + maxLength);
    }
}

This solution has a time complexity of O(n), where n is the length of the input word, as we only iterate through the word once. The space complexity is O(k), where k is the number of elements in the forbidden array, as we use a set to store the forbidden strings and another set for the sliding window.