[Java] 🍀🍀🍀 Prefix sum and some fun
Code\njava []\nclass Solution {\n\n  int n;\n  int m;\n  int[] covers;\n\n  public int[] validSequence(String word1, String word2) {\n    n = word1.length();\n 
# Code\n```java []\nclass Solution {\n\n  int n;\n  int m;\n  int[] covers;\n\n  public int[] validSequence(String word1, String word2) {\n    n = word1.length();\n    m = word2.length();\n    covers = new int[n];\n    int j = m - 1;\n    for (int i = n - 1; i >= 0; i--) {\n      if (j >= 0 && word1.charAt(i) == word2.charAt(j)) {\n        covers[i] = i == n - 1 ? 1 : covers[i + 1] + 1;\n        j--;\n      } else {\n        covers[i] = i == n - 1 ? 0 : covers[i + 1];\n      }\n    }\n    j = 0;\n    List<Integer> result = new ArrayList<>();\n    int victory = -1;\n    for (int i = 0; i < n; i++) {\n      if (word1.charAt(i) == word2.charAt(j)) {\n        result.add(i);\n        j++;\n        if (j == m) {\n          break;\n        }\n      } else {\n        if ((i == n - 1 ? 0 : covers[i + 1]) >= m - j - 1) {\n          result.add(i);\n          j++;\n          victory = i + 1;\n          break;\n        }\n      }\n    }\n    if (result.size() == m) {\n      return result.stream().mapToInt(Integer::intValue).toArray();\n    }\n    if (victory == -1) {\n      return new int[0];\n    }\n    for (int i = victory; i < n; i++) {\n      if (word1.charAt(i) == word2.charAt(j)) {\n        result.add(i);\n        j++;\n      }\n      if (j == m) {\n        break;\n      }\n    }\n    return result.size() == m ? result.stream().mapToInt(Integer::intValue).toArray() : new int[0];\n  }\n}\n```
['Java']