LeetCode Entry
2825. Make String a Subsequence Using Cyclic Increments
Increase some chars once to make a subsequence
2825. Make String a Subsequence Using Cyclic Increments medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/822
Problem TLDR
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 its 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();
}