Greedy C++ solution | Code comments
Intuition\nEfficiently finds the lexicographically smallest valid sequence of indices if one exists.\n\n# Approach\n1. Matching characters from the end: In the 
# Intuition\nEfficiently finds the lexicographically smallest valid sequence of indices if one exists.\n\n# Approach\n1. Matching characters from the end: In the first loop, we find the last occurrence of each character in word2 in word1, starting from the end of both strings. This helps in ensuring we find the lexicographically smallest sequence.\n\n2. Constructing the valid sequence: In the second loop, we try to match characters from word1 to word2. If there\'s a mismatch and we haven\'t changed any character yet, we allow one change as per the problem\'s requirements.\n\n3. Checking conditions for valid sequence: We check that we can always move forward in word2 without skipping any characters that we need to match.\n\n# Complexity\n- Time complexity: O(n + n)\n\n- Space complexity: O(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int n = word2.size();  // Length of word2\n        int m = word1.size();  // Length of word1\n        \n        // Array to store the last occurrence of each character in word2 in word1\n        vector<int> last(n, -1);  \n        int j = n - 1;  // Pointer to traverse word2 from right to left\n\n        // Traverse word1 from the end to the beginning\n        for (int i = m - 1; i >= 0; i--) {\n            // If characters match and we haven\'t yet found all characters in word2\n            if (j >= 0 && word1[i] == word2[j]) {\n                last[j] = i;  // Store the index in word1 where word2[j] is found\n                j--;  // Move to the next character in word2\n            }\n        }\n\n        j = 0;  // Reset pointer to traverse word2 from left to right\n        int flag = 1;  // Flag to track if one character has been changed\n        vector<int> ans;  // To store the valid sequence of indices\n\n        // Traverse word1 from the beginning\n        for (int i = 0; i < m; i++) {\n            if (j < n) {  // If we haven\'t matched all characters in word2\n                // Check if current word1[i] matches word2[j] or if we can change it\n                if (word1[i] == word2[j] || (flag == 1 && (j == n - 1 || i + 1 <= last[j + 1]))) {\n                    if (word1[i] != word2[j]) {\n                        flag = 0;  // Mark that we\'ve changed one character\n                    }\n                    ans.push_back(i);  // Add the index to the result\n                    j++;  // Move to the next character in word2\n                }\n            }\n        }\n        \n        // Return the result if we\'ve matched all characters in word2, otherwise return an empty vector\n        return (j == n) ? ans : vector<int>();\n    }\n};\n\n```
['C++']