2825. Make String a Subsequence Using Cyclic Increments

MediumView on LeetCode

Two Pointers String

Time: O(|str1|)

Space: O(1)

Intuition

Check if string s can become t by rotating t (i.e., t is a rotation of s). Standard rotation check: s == t or s in t+t.

Algorithm

1If s.length != t.length: false. Return (t+t).contains(s).

Common Pitfalls

•Rotation: t is a rotation of s iff s appears in t+t. Length must match.

2825.cs

// Approach: Two-pointer; advance str2 pointer when str1[i] matches str2[j] exactly or cyclically.
// Time: O(|str1|) Space: O(1)

public class Solution
{
    public bool CanMakeSubsequence(string str1, string str2)
    {
        int i = 0; // str2's index

        foreach (char c in str1)
        {
            if (c == str2[i] || ((char)('a' + ((c - 'a' + 1) % 26)) == str2[i]))
            {
                if (++i == str2.Length)
                    return true;
            }
        }

        return false;
    }
}

Was this solution helpful?