DEV Community

Nilesh Raut
Nilesh Raut

Posted on • Edited on • Originally published at nileshblog.tech

1 1 1 1 1

Cracking the LeetCode:392 Is Subsequence?

What is LeetCode 392: Is Subsequence?
Before we dive into the intricacies of LeetCode 392, let's grasp the concept. This coding challenge, categorized as "easy," tests our ability to determine if one string is a subsequence of another. Think of it as a detective's quest to find clues in a larger mystery.
Unpacking the Challenge
Imagine you have two strings: s and t. Your task is to check whether s is a subsequence of t. In other words, can we derive string s by deleting some (or none) characters from string t while maintaining the order of characters in s? If we can, the answer is "yes"; otherwise, it's "no."
To illustrate this, let's look at an example:
Example:

  • s: "abc"
  • t: "ahbgdc" In this case, the answer is "yes" because we can delete characters from t to form s. We can remove 'h' and 'g,' leaving us with "abc." The Approach: Greedy is the Key To tackle this problem efficiently, we'll adopt a greedy approach. Think of it as picking the ripest fruit from a tree. Here's the plan:
  • Initialize two pointers, one for each string: i for s and j for t.
  • Traverse both strings using these pointers.
  • Compare characters at the current positions of i and j.
  • If they match, move both pointers forward.
  • If they don't match, only move the j pointer.
  • Keep doing this until you reach the end of either string. If you successfully traverse the entire s string, it means s is a subsequence of t. If the j pointer reaches the end of t before i finishes with s, then it's not a subsequence. Time Complexity Matters Our approach is efficient with a time complexity of O(m + n), where m is the length of s and n is the length of t. We traverse both strings only once, making this a linear time solution. Coding It Out Let's put theory into practice with some Python code: pythonCopy codedef isSubsequence(s, t): i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)

Conclusion: Cracked the Code
LeetCode 392. Is Subsequence ," is a problem that can be efficiently solved using a simple greedy approach. By comparing characters of both strings, we can determine whether one is a subsequence of the other. Remember, it's not about brute force; it's about being smart and efficient, just like a detective solving a case.
So, the next time you encounter this problem, don't be intimidated. You've got the code-cracking skills to answer, "Is Subsequence?" with confidence. Happy coding!

Top comments (0)

Great read:

Is it Time to go Back to the Monolith?

History repeats itself. Everything old is new again and I’ve been around long enough to see ideas discarded, rediscovered and return triumphantly to overtake the fad. In recent years SQL has made a tremendous comeback from the dead. We love relational databases all over again. I think the Monolith will have its space odyssey moment again. Microservices and serverless are trends pushed by the cloud vendors, designed to sell us more cloud computing resources.

Microservices make very little sense financially for most use cases. Yes, they can ramp down. But when they scale up, they pay the costs in dividends. The increased observability costs alone line the pockets of the “big cloud” vendors.