Skip to content

3302. Find the Lexicographically Smallest Valid Sequence 👍

  • Time: $O(|\texttt{word1}| + |\texttt{word2}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<int> validSequence(string word1, string word2) {
    vector<int> ans(word2.length());
    // last[j] := the index i of the last occurrence in word1, where
    // word1[i] == word2[j]
    vector<int> last(word2.length(), -1);

    int i = word1.length() - 1;
    int j = word2.length() - 1;
    while (i >= 0 && j >= 0) {
      if (word1[i] == word2[j])
        last[j--] = i;
      --i;
    }

    bool canSkip = true;
    j = 0;
    for (i = 0; i < word1.length(); ++i) {
      if (j == word2.length())
        break;
      if (word1[i] == word2[j]) {
        ans[j++] = i;
      } else if (canSkip && (j == word2.length() - 1 || i < last[j + 1])) {
        canSkip = false;
        ans[j++] = i;
      }
    }

    return j == word2.length() ? ans : vector<int>();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int[] validSequence(String word1, String word2) {
    int[] ans = new int[word2.length()];
    // last[j] := the index i of the last occurrence in word1, where
    // word1[i] == word2[j]
    int[] last = new int[word2.length()];
    Arrays.fill(last, -1);

    int i = word1.length() - 1;
    int j = word2.length() - 1;
    while (i >= 0 && j >= 0) {
      if (word1.charAt(i) == word2.charAt(j))
        last[j--] = i;
      --i;
    }

    boolean canSkip = true;
    j = 0;
    for (i = 0; i < word1.length(); ++i) {
      if (j == word2.length())
        break;
      if (word1.charAt(i) == word2.charAt(j)) {
        ans[j++] = i;
      } else if (canSkip && (j == word2.length() - 1 || i < last[j + 1])) {
        canSkip = false;
        ans[j++] = i;
      }
    }

    return j == word2.length() ? ans : new int[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def validSequence(self, word1: str, word2: str) -> list[int]:
    ans = []
    # last[j] := the index i of the last occurrence in word1, where
    # word1[i] == word2[j]
    last = [-1] * len(word2)

    i = len(word1) - 1
    j = len(word2) - 1
    while i >= 0 and j >= 0:
      if word1[i] == word2[j]:
        last[j] = i
        j -= 1
      i -= 1

    canSkip = True
    j = 0
    for i, c in enumerate(word1):
      if j == len(word2):
        break
      if c == word2[j]:
        ans.append(i)
        j += 1
      elif canSkip and (j == len(word2) - 1 or i < last[j + 1]):
        canSkip = False
        ans.append(i)
        j += 1

    return ans if j == len(word2) else []