Python code with great clarity || beats 100% || prefix and suffix
Before diving into the solution, one should be very careful that "Note that the answer must represent the lexicographically smallest array, not the correspondin
Before diving into the solution, one should be very careful that "Note that the answer must represent the lexicographically smallest array, **not the corresponding string formed by those indices**." As for greedy selection, I mean the character of word1 is selected if it is the same as that of word2 otherwise skip it in word1.\n\nThen, we talk about how to solve the question:\n\n**Main Idea**:\nFrom word1, we greedily select from the beggining and ending of word1, and keep recording how many prefix and suffix characters of word2 can be constructed directly from both sides of word1.\nFor example:\nIf word1 is a string of size **n**, word2 is a string of size **m**, we construct a prefix array and a suffix array of size **n** respectively.\nAt position i (0~n-1), prefix[i] represents the number of characters of prefix word2 can be matched from the characters prior to i (0~i-1) in word1; suffix[i] represents the number of characters of suffix word2 can be matched from the characters succeeding i (i+1~n-1) in word1.\n\nOnce the two arrays are constructed, we greedily select prefix characters from word1 and append to the answer. However, If at position i, suffix[i] + prefix[i] >= m, we can append position i to the answer no matter if word1[i] matches word2[prefix[i]]. However, such operation is only allowed by one time if a mismatch happend.\n\nAt the time of returning, if the length of the answer is less than **m**, if failed and return an empty array, otherwise, return answer.\n\nHere\'s the demonstration of examples from description. \nword1: "vbcca", word2: "abc", prefix: [0, 0, 0, 0, 0], suffix: [2, 1, 1, 0, 0], answer: [0, 1, 2]\nword1: "bacdc", word2: "abc", prefix: [0, 0, 1, 1, 1], suffix: [1, 1, 1, 1, 0], answer: [1, 2, 4]\nword1: "aaaaaa", word2: "aaabc", prefix: [0, 1, 2, 3, 3, 3], suffix: [0, 0, 0, 0, 0, 0], answer: [0, 1, 2] (<5)\nword1: "abc", word2: "ab", prefix: [0, 1, 2], suffix: [1, 0, 0], answer: [0,1]\n\nTime complexity: O(n)\nSpace complexity: O(n)\n\n```\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n, m = len(word1), len(word2)\n        \n        j = m-1\n        suff = [0]*n\n        for i in reversed(range(1, n)):\n            suff[i-1] = suff[i]\n            if j>=0 and word1[i] == word2[j]:\n                suff[i-1] += 1\n                j -= 1\n        \n        j = 0\n        pref = [0]*n\n        for i in range(n-1):\n            pref[i+1] = pref[i]\n            if j<m and word1[i] == word2[j]:\n                pref[i+1] += 1\n                j += 1\n                \n        j = 0\n        ans = []\n        allowed = False # if there exist one character in answer that is not identical to the character at the corresponding position of word2\n        for i in range(n):\n            if j>=m:\n                break\n            if word1[i] == word2[j] or (pref[i]+suff[i]>=m-1 and not allowed):\n                if word1[i] != word2[j]:\n                    allowed = True\n                ans.append(i)\n                j += 1\n\n        return ans if len(ans)==m else []\n```
['Greedy', 'Suffix Array', 'Python3']