Increase some chars once to make a subsequence #medium
Intuition
Attention to the description:
subsequence vs substring
rotation at most once
any positions
Let's scan over str2 (resulting subsequence) and greedily find positions in str1 for each of its letters. Compare the char and it’s rolled down version.
Approach
trick from Lee: (s2[i] - s1[j]) <= 1 (with % 26 added for 'a'-'z' case)
Complexity
Time complexity: $$O(n + m)$$
Space complexity: $$O(1)$$
Code
fun canMakeSubsequence(str1: String, str2: String): Boolean {
var j = 0; var i = 0
while (i < str2.length && j < str1.length)
if ((str2[i] - str1[j] + 26) % 26 <= 1) { ++i; ++j } else ++j
return i == str2.length
}
pub fn can_make_subsequence(str1: String, str2: String) -> bool {
k
while i < s2.len() && j < s1.len() {
if (s2[i] - s1[j] + 26) % 26 <= 1 { i += 1; j += 1 } else { j += 1 }
}; i == s2.len()
}
bool canMakeSubsequence(string s1, string s2) {
int i = 0;
for (int j = 0; j < s1.size() && i < s2.size(); ++j)
if ((s2[i] - s1[j] + 26) % 26 <= 1) ++i;
return i == s2.size();
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
