You are given two 0-indexed strings str1
and str2
.
In an operation, you select a set of indices in str1
, and for each index i
in the set, increment str1[i]
to the next character cyclically. That is 'a'
becomes 'b'
, 'b'
becomes 'c'
, and so on, and 'z'
becomes 'a'
.
Return true
if it is possible to make str2
a subsequence of str1
by performing the operation at most once, and false
otherwise.
Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
Input: str1 = "abc", str2 = "ad" Output: true Explanation: Select index 2 in str1. Increment str1[2] to become 'd'. Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.
Example 2:
Input: str1 = "zc", str2 = "ad" Output: true Explanation: Select indices 0 and 1 in str1. Increment str1[0] to become 'a'. Increment str1[1] to become 'd'. Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.
Example 3:
Input: str1 = "ab", str2 = "d" Output: false Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. Therefore, false is returned.
Constraints:
1 <= str1.length <= 105
1 <= str2.length <= 105
str1
andstr2
consist of only lowercase English letters.
Solution: Two pointers
s1[i] and s2[j] can match if
s1[i] == s2[j] or inc(s1[i]) == s2[j]
If matched: ++i; ++j else ++i.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 |
class Solution { public: bool canMakeSubsequence(string_view s1, string_view s2) { for (int i = 0, j = 0, n = s1.size(), m = s2.size(); i < n; ++i) if (s1[i] == s2[j] || (s1[i] - 'a' + 1) % 26 == s2[j] - 'a') if (++j == m) return true; return false; } }; |
Iterator version
C++
1 2 3 4 5 6 7 8 9 |
class Solution { public: bool canMakeSubsequence(string_view s1, string_view s2) { for (auto i = begin(s1), j = begin(s2); i != end(s1); ++i) if (*i == *j || (*i - 'a' + 1) % 26 == *j - 'a') if (++j == end(s2)) return true; return false; } }; |