PreComputing
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen we iterate the ith element of word1, we want to know if the remaining substring of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen we iterate the ith element of `word1`, we want to know if the remaining substring of `word1` can match the rest substring of `word2`. So, we can pre-compute `cover[i]` to track the suffix length of `word2` that can be matched by substring `word1[i:]`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$: `n = strlen(word1)`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$: `n = strlen(word1)`\n\n# Code\n```c []\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\nint* validSequence(char* word1, char* word2, int* returnSize) {\n    int wd1_len = strlen(word1);\n    int wd2_len = strlen(word2);\n    int cover[wd1_len + 1];\n    cover[wd1_len] = 0;\n    /* Pre-compute the `cover` array */\n    for (int i = wd1_len - 1, j = wd2_len - 1; i >= 0; i--)\n    {\n        if (j > 0 && word1[i] == word2[j])\n        {\n            cover[i] = 1 + cover[i + 1];\n            j--;\n        }\n        else\n        {\n            cover[i] = cover[i + 1];\n        }\n    }\n    \n    /* Find the lexicographically smallest result */\n    int *ret = malloc(wd2_len * sizeof(int));\n    bool modify = true;\n    int i = 0, j = 0;\n    *returnSize = 0;\n    while (i < wd1_len && j < wd2_len)\n    {\n        if (word1[i] == word2[j])\n        {\n            ret[(*returnSize)++] = i;\n            j++;\n        }\n        else\n        {\n            if (modify && (i + 1 < wd1_len) && (cover[i + 1] >= wd2_len - j - 1))\n            {\n                modify = false;\n                ret[(*returnSize)++] = i;\n                j++;\n            }\n        }\n        i++;\n    }\n    if (j != wd2_len)\n    {\n        *returnSize = 0;\n    }\n\n    return ret;\n}\n```
['C']