2781. Length of the Longest Valid Substring

1. g[i], f[i] 的關係還是沒有很懂 
2. 下面的 case 會 fails
"cbaaaabc"
["aaa","cb"]

f[i] : 在 s[i] 開頭，最短的 forbidden string 長度
g[i] : 以 i 開頭的最長合法 substring 長度


forbidden : ["de", "le", "e"]


index: 0 1 2 3 4 5 6 7
s[i] : l e e t c o d e
f[i] : 2 1 1 x x x 2 1
g[i] : 1 0 0 4 3 2 1 0


g[i+1] = \min_{j>=i+1} { j + f[j] - 1 } - (i+1)
g[i] =   \min_{j>=i  } { j + f[j] - 1 } - i


Trie


class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> forbiddenSet = new HashSet<>();
        forbiddenSet.addAll(forbidden);
        
        int n = word.length();
        int [] f = new int [n];
        Arrays.fill(f, Integer.MAX_VALUE/2);
        
        for(int i = 0; i < n; i ++){
           for(int j = i; j <= n; j++){
               String str = word.substring(i, j);
               if(forbiddenSet.contains(str)){
                  f[i] = Math.min(f[i], str.length());  
               }
           } 
        }
        
        int g[] = new int [n];
         Arrays.fill(g, Integer.MAX_VALUE/2);
       
        int max = 0;
        
        for(int i = 0; i < n; i ++){
           for(int j = i; j < n; j ++){
              if(j + f[j]  - i >= 0){
                 g[i] = Math.min(g[i], j + f[j] - 1 - i);
              } 
          
           } 
           if(g[i] != Integer.MAX_VALUE/2) 
               max = Math.max(max, g[i]); 
        }
        /*
        f[i] : 在 s[i] 開頭，最短的 forbidden string 長度
        g[i] : 以 i 開頭的最長合法 substring 長度

        */

        // System.out.println(Arrays.toString(f));
        // System.out.println(Arrays.toString(g));
        return max;
    }
}

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> visited = new HashSet<>(forbidden);
        
        int n = word.length();
        int size = 0;
        
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < n; i++){
            sb.append(word.charAt(i)+"");
            int len = sb.length();
            for(int j = len - 1; j >= Math.max(0, len - 10); j --){
                String str = sb.substring(j);
               
                if(visited.contains(str)){
                    //  為什麼這裡會這樣寫
                    //  System.out.println("before:" +  sb.toString());
                    // System.out.println(str);
                    sb.delete(0, j + 1);
                    // System.out.println("after:" + sb.toString()); 
                    break;
                }
            }
            // System.out.println("result:" + sb.toString()); 
            
            // sb 是以 i 結尾的最長合法 substring
            
            // 1 2 [3 4 5 7 8] 9 10 11 12
            // 1 2 [3 4 5 7 8 9] 10 11 12
            
            size = Math.max(size, sb.length());
            
        }
        return size;
    }
}

### 2781 AC

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> forbiddenSet = new HashSet<>();
        forbiddenSet.addAll(forbidden);
        
        int n = word.length();
        int [] f = new int [n];
        Arrays.fill(f, Integer.MAX_VALUE/2);
        
        for(int i = 0; i < n; i ++){
           for(int j = i; j <= n && j <= i + 10; j++){
               String str = word.substring(i, j);
               if(forbiddenSet.contains(str)){
                  f[i] = Math.min(f[i], str.length());  
               }
           } 
        }
        
        int g[] = new int [n];
         Arrays.fill(g, Integer.MAX_VALUE/2);
       
        int max = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            g[i] = n - i;
            if (i + 1 < n) g[i] = Math.min(g[i], g[i+1] + 1);
            g[i] = Math.min(g[i], f[i] - 1); // i 開頭的 forbidden string
            max = Math.max(max, g[i]); 
        }
        /*
        f[i] : 在 s[i] 開頭，最短的 forbidden string 長度
        g[i] : 以 i 開頭的最長合法 substring 長度

        */

        // System.out.println(Arrays.toString(f));
        // System.out.println(Arrays.toString(g));
        return max;
    }
}

/*
     i :  0 1 2 3 4 5 6 7
   s[i]:  c b a a a a b c
   f[i]:  2 x 3 3 x x x x
   g[i]:  1 3 2 2 x x x x


   f[i] : 以 i 開頭最短的 forbidden
   g[i] = \min (n-i) ,\min_{j>=i} { j + f[j] - 1 - i }


   g[i-1] = \min (n-(i-1)), \min_{j>=(i-1)} { j + f[j] - 1 - (i-1) }
          = \min (n-(i)), \min_{j>=i} { j + f[j] - 1 - i} + 1, f[i-1]-1
          = \min g[i] + 1, f[i-1]-1
*/