Question

Formatted question description: https://leetcode.ca/all/392.html

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

0 <= s.length <= 100
0 <= t.length <= 10⁴
s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s₁, s₂, ..., s_k where k >= 10⁹, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Algorithm

The two pointers point to the strings s and t respectively, and then if the characters are equal, i and j are incremented by 1, otherwise only j increments by 1.

Finally, see if i is equal to the length of s, which means that s has been traversed, and the characters are all appeared in t.

Follow up

Follow up in the topic said that if there are a large number of strings s, ask us how to optimize.

So since the string t is always the same, we can do some pre-processing on t. Although the subsequence does not need to be a contiguous substring, but the order between characters is required, then we can establish a direct mapping

from: each character in the string t
to: its position

Since there may be repeated characters in t, all positions where the same character appears are added to an array in order.

Therefore, HashMap is used to establish the mapping between each character and its position array.

Then iterate over each character in the string s:

For each traversed character c, we search in the corresponding character array in HashMap.
Since the position array is ordered, we use binary search to speed up the search.

It should be noted here that because the subsequence is ordered, a variable pre is needed to record the position of the current match in the t string. For the character c in the current s string, even if it exists in the t string, if It cannot be matched before the position pre.

So we can use uppper_bound() to find the first position greater than pre in binary, If it does not exist, return false directly, otherwise, update pre to the result of binary search and continue the loop.

This approach has a pre-processing time complexity of O(m) where m is the length of T. The time complexity for each incoming string S is O(n) where n is the length of S. The space complexity is O(m*k) to store the index for all S strings.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Is_Subsequence {
    class Solution {
        public boolean isSubsequence(String s, String t) {
            if (s == null || s.length() == 0) {
                return true;
            }

            int i = 0;
            for (int j = 0; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    i++;

                    if (i == s.length()) { // last char is matched
                        return true;
                    }
                }
            }

            return false;
        }
    }


    class Solution_followup {
        public boolean isSubsequence(String s, String t) {
            // step 1: save all the index for the t
            Map<Character, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                if (!map.containsKey(c)) {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    map.put(c, pos);
                } else {
                    List<Integer> pos = map.get(c);
                    pos.add(i);
                    // map.put(c, pos);
                }
            }

            // step 2: for each char in s, find the first index
            int prevIndex = -1;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                List<Integer> pos = map.get(c);
                if (pos == null || pos.size() == 0) {
                    return false;
                }

                int currentIndex = getNextIndexGreaterThanTarget(pos, prevIndex);

                if (currentIndex == -1) {
                    return false;
                }

                prevIndex = currentIndex;
            }

            return true;
        }

        // find next number greater than target
        // if not found, return -1
        private int getNextIndexGreaterThanTarget(List<Integer> pos, int targetIndex) {
            int lo = 0;
            int hi = pos.size() - 1;

            while (lo + 1 <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (pos.get(mid) == targetIndex) {
                    lo = mid + 1;
                } else if (pos.get(mid) > targetIndex) {
                    hi = mid;
                } else if (pos.get(mid) < targetIndex) {
                    lo = mid + 1;
                }
            }

            if (pos.get(lo) > targetIndex) {
                return pos.get(lo);
            }

            if (pos.get(hi) > targetIndex) {
                return pos.get(hi);
            }

            return -1;
        }
    }
}

############

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
            ++j;
        }
        return i == m;
    }
}

// OJ: https://leetcode.com/problems/is-subsequence/
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0, M = s.size(), N = t.size();
        for (; i < M && j < N; ++j) {
            if (s[i] == t[j]) ++i;
        }
        return i == M;
    }
};

'''
>>> a=[1,2,3,1,2,3,1,2,3]
>>> bisect.bisect_left(a, 2)
1
>>> bisect.bisect_right(a, 2)
8
'''
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j, m, n = 0, 0, len(s), len(t)
        while i < m and j < n:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == m

# follow up
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # pre-processing step
        index = defaultdict(list)
        for i, c in enumerate(t):
            index[c].append(i)
        
        # iterate through each incoming string s
        j = 0
        for c in s:
            if c not in index:
                return False
            pos_list = index[c]
            pos = bisect_left(pos_list, j)
            if pos == len(pos_list):
                return False
            j = pos_list[pos] + 1
        return True

func isSubsequence(s string, t string) bool {
	i, j, m, n := 0, 0, len(s), len(t)
	for i < m && j < n {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == m
}

function isSubsequence(s: string, t: string): boolean {
    let m = s.length,
        n = t.length;
    let i = 0;
    for (let j = 0; j < n && i < m; ++j) {
        if (s.charAt(i) == t.charAt(j)) {
            ++i;
        }
    }
    return i == m;
}

impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        let (s, t) = (s.as_bytes(), t.as_bytes());
        let n = t.len();
        let mut i = 0;
        for &c in s.iter() {
            while i < n && t[i] != c {
                i += 1;
            }
            if i == n {
                return false;
            }
            i += 1;
        }
        true
    }
}

public class Solution {
    public bool IsSubsequence(string s, string t) {
        int m = s.Length, n = t.Length;
        int i = 0, j = 0;
        for (; i < m && j < n; ++j) {
            if (s[i] == t[j]) {
                ++i;
            }
        }
        return i == m;
    }
}

392 - Is Subsequence

Question

Algorithm

Follow up

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Follow up

Code

All Problems

All Solutions