Skip to content

3302. Find the Lexicographically Smallest Valid Sequence

Description

You are given two strings word1 and word2.

A string x is called almost equal to y if you can change at most one character in x to make it identical to y.

A sequence of indices seq is called valid if:

  • The indices are sorted in ascending order.
  • Concatenating the characters at these indices in word1 in the same order results in a string that is almost equal to word2.

Return an array of size word2.length representing the lexicographically smallest valid sequence of indices. If no such sequence of indices exists, return an empty array.

Note that the answer must represent the lexicographically smallest array, not the corresponding string formed by those indices.

 

Example 1:

Input: word1 = "vbcca", word2 = "abc"

Output: [0,1,2]

Explanation:

The lexicographically smallest valid sequence of indices is [0, 1, 2]:

  • Change word1[0] to 'a'.
  • word1[1] is already 'b'.
  • word1[2] is already 'c'.

Example 2:

Input: word1 = "bacdc", word2 = "abc"

Output: [1,2,4]

Explanation:

The lexicographically smallest valid sequence of indices is [1, 2, 4]:

  • word1[1] is already 'a'.
  • Change word1[2] to 'b'.
  • word1[4] is already 'c'.

Example 3:

Input: word1 = "aaaaaa", word2 = "aaabc"

Output: []

Explanation:

There is no valid sequence of indices.

Example 4:

Input: word1 = "abc", word2 = "ab"

Output: [0,1]

 

Constraints:

  • 1 <= word2.length < word1.length <= 3 * 105
  • word1 and word2 consist only of lowercase English letters.

Solutions

Solution 1: Greedy + Two Pointers

We first use two pointers to preprocess a suffix array \(\textit{suf}\) from right to left, where \(\textit{suf}[i]\) represents the smallest starting index in \(\textit{word2}\) such that \(\textit{word2}[\textit{suf}[i]:]\) is a subsequence of \(\textit{word1}[i:]\). Specifically, we use a pointer \(j\) pointing to the frontmost unmatched character in \(\textit{word2}\), initially \(j = n - 1\), and set \(\textit{suf}[m] = n\). Starting from \(i = m - 1\), we traverse \(\textit{word1}\) from right to left. If \(j \ge 0\) and \(\textit{word1}[i] = \textit{word2}[j]\), it means \(\textit{word2}[j]\) can be matched, so we decrement \(j\) by one, and then set \(\textit{suf}[i] = j + 1\).

Next, we traverse \(\textit{word1}\) from left to right, using a pointer \(j\) to denote the index of the character in \(\textit{word2}\) that we currently need to match (initially \(j = 0\)), and a variable \(\textit{changed}\) to record whether we have already modified a character. For each character \(c\) at index \(i\):

  • If \(c = \textit{word2}[j]\), choosing index \(i\) is always no worse (the smaller the index, the smaller the lexicographical order of the sequence), so we directly add \(i\) to the answer and increment \(j\) by one;
  • Otherwise, if we have not modified a character yet and \(\textit{suf}[i+1] \le j + 1\), it means we can modify \(\textit{word1}[i]\) to \(\textit{word2}[j]\), and the remaining part \(\textit{word2}[j+1:]\) can still be matched within \(\textit{word1}[i+1:]\). In this case, we choose index \(i\) and set \(\textit{changed}\) to true.

When \(j = n\), we have matched all of \(\textit{word2}\) and can return the answer. If the traversal ends without completing the match, we return an empty array.

The time complexity is \(O(m + n)\), and the space complexity is \(O(m)\), where \(m\) and \(n\) are the lengths of the strings \(\textit{word1}\) and \(\textit{word2}\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        m, n = len(word1), len(word2)
        suf = [0] * (m + 1)
        suf[m] = n
        j = n - 1
        for i in range(m - 1, -1, -1):
            if j >= 0 and word1[i] == word2[j]:
                j -= 1
            suf[i] = j + 1

        ans = []
        changed = False
        j = 0
        for i, c in enumerate(word1):
            if c == word2[j] or (not changed and suf[i + 1] <= j + 1):
                if c != word2[j]:
                    changed = True
                ans.append(i)
                j += 1
                if j == n:
                    return ans
        return []

 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
33
34
35
36
37
class Solution {
    public int[] validSequence(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        int[] suf = new int[m + 1];
        suf[m] = n;

        int j = n - 1;
        for (int i = m - 1; i >= 0; i--) {
            if (j >= 0 && word1.charAt(i) == word2.charAt(j)) {
                j--;
            }
            suf[i] = j + 1;
        }

        int[] ans = new int[n];
        int size = 0;
        boolean changed = false;
        j = 0;

        for (int i = 0; i < m; i++) {
            char c = word1.charAt(i);
            if (c == word2.charAt(j) || (!changed && suf[i + 1] <= j + 1)) {
                if (c != word2.charAt(j)) {
                    changed = true;
                }
                ans[size++] = i;
                j++;
                if (j == n) {
                    return ans;
                }
            }
        }

        return 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
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int m = word1.size(), n = word2.size();

        vector<int> suf(m + 1);
        suf[m] = n;

        int j = n - 1;
        for (int i = m - 1; i >= 0; i--) {
            if (j >= 0 && word1[i] == word2[j]) {
                j--;
            }
            suf[i] = j + 1;
        }

        vector<int> ans;
        bool changed = false;
        j = 0;

        for (int i = 0; i < m; i++) {
            char c = word1[i];
            if (c == word2[j] || (!changed && suf[i + 1] <= j + 1)) {
                if (c != word2[j]) {
                    changed = true;
                }
                ans.push_back(i);
                j++;

                if (j == n) {
                    return ans;
                }
            }
        }

        return {};
    }
};

 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
33
34
35
func validSequence(word1 string, word2 string) []int {
    m, n := len(word1), len(word2)

    suf := make([]int, m+1)
    suf[m] = n

    j := n - 1
    for i := m - 1; i >= 0; i-- {
        if j >= 0 && word1[i] == word2[j] {
            j--
        }
        suf[i] = j + 1
    }

    ans := make([]int, 0, n)
    changed := false
    j = 0

    for i := 0; i < m; i++ {
        c := word1[i]
        if c == word2[j] || (!changed && suf[i+1] <= j+1) {
            if c != word2[j] {
                changed = true
            }
            ans = append(ans, i)
            j++

            if j == n {
                return ans
            }
        }
    }

    return []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
33
34
35
36
37
38
function validSequence(word1: string, word2: string): number[] {
    const m = word1.length;
    const n = word2.length;

    const suf = new Array<number>(m + 1).fill(0);
    suf[m] = n;

    let j = n - 1;
    for (let i = m - 1; i >= 0; i--) {
        if (j >= 0 && word1[i] === word2[j]) {
            j--;
        }
        suf[i] = j + 1;
    }

    const ans: number[] = [];
    let changed = false;
    j = 0;

    for (let i = 0; i < m; i++) {
        const c = word1[i];

        if (c === word2[j] || (!changed && suf[i + 1] <= j + 1)) {
            if (c !== word2[j]) {
                changed = true;
            }

            ans.push(i);
            j++;

            if (j === n) {
                return ans;
            }
        }
    }

    return [];
}

 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
33
34
35
36
37
38
39
impl Solution {
    pub fn valid_sequence(word1: String, word2: String) -> Vec<i32> {
        let word1_bytes = word1.as_bytes();
        let word2_bytes = word2.as_bytes();
        let mut positions = vec![-1i32; word2_bytes.len()];
        let mut word2_index = word2_bytes.len() as isize - 1;
        let mut word1_index = word1_bytes.len() as isize - 1;
        while word1_index >= 0 && word2_index >= 0 {
            if word1_bytes[word1_index as usize] == word2_bytes[word2_index as usize] {
                positions[word2_index as usize] = word1_index as i32;
                word2_index -= 1;
            }
            word1_index -= 1;
        }
        let mut mismatch_available = true;
        let mut matched_count = 0usize;
        for (index, &byte) in word1_bytes.iter().enumerate() {
            if matched_count == word2_bytes.len() {
                break;
            }
            if byte == word2_bytes[matched_count] {
                positions[matched_count] = index as i32;
                matched_count += 1;
            } else if mismatch_available
                && (matched_count + 1 == word2_bytes.len()
                    || (index as i32) < positions[matched_count + 1])
            {
                mismatch_available = false;
                positions[matched_count] = index as i32;
                matched_count += 1;
            }
        }
        if matched_count == word2_bytes.len() {
            positions
        } else {
            Vec::new()
        }
    }
}

Comments